一.单链表
package com.bzw.linkedlist; import java.util.Stack; public class SingleLinkedList { public static void main(String[] args) { Hero hero1 = new Hero(1, "宋江", "及时雨"); Hero hero2 = new Hero(2, "卢俊义", "玉麒麟"); Hero hero3 = new Hero(3, "吴用", "智多星"); Hero hero4 = new Hero(4, "林冲", "豹子头"); Hero hero5 = new Hero(5, "小卢", "玉麒麟~~"); Hero hero6 = new Hero(6, "小卢", "玉麒麟~~"); SingleLinked singleLinked = new SingleLinked(); SingleLinked singleLinked1 = new SingleLinked(); // singleLinked.addHero(hero2); // singleLinked.addHero(hero3); // singleLinked.addHero(hero4); // singleLinked.addHero(hero1); singleLinked.addHeroByOrder(hero3); singleLinked.addHeroByOrder(hero2); singleLinked1.addHeroByOrder(hero4); singleLinked.addHeroByOrder(hero1); singleLinked.addHeroByOrder(hero5); singleLinked1.addHeroByOrder(hero6); // singleLinked.addHeroByOrder(hero4); // singleLinked.showHero(); // singleLinked.update(hero5); // singleLinked.delete(hero4); singleLinked.showHero(); System.out.println(); singleLinked1.showHero(); //练习题 // System.out.println("有效结点数" getLength(singleLinked.getHead())); // // System.out.println(findNode(singleLinked.getHead(),4)); // reverseLinkedList(singleLinked.getHead()); // singleLinked.showHero(); // reversePrint(singleLinked.getHead()); jojnLinkedList(singleLinked.getHead(), singleLinked1.getHead()); System.out.println(); singleLinked.showHero(); } //链表有效结点个数 public static int getLength(Hero head) { if (head.next == null) { System.out.println("链表为空"); return 0; } Hero temp = head.next; int count = 0; while (temp != null) { count ; temp = temp.next; } return count; } ///查询倒数第K结点 public static Hero findNode(Hero head, int index) { if (head.next == null) { System.out.println("空链表"); } int size = getLength(head); Hero temp = head.next; if (index < 0 || index > size) { return null; } for (int i = 0; i < size - index; i ) { temp = temp.next; } System.out.println("倒数第" index "个结点："); return temp; } ///反转链表 public static void reverseLinkedList(Hero head) { if (head.next == null) { System.out.println("空链表"); } Hero temp = head.next; Hero next = null; //temp 下一个结点(非常重要的指针(变量)，不需要这个变量temp.next如果存起来，单链表就会断裂) Hero newHead = new Hero(0, "", ""); while (temp != null) { next = temp.next; temp.next = newHead.next; //temp下一个结点指向新链表的前端。(实际上是将新加入的结点与后面的结点连接起来) newHead.next = temp; temp = next; } head.next = newHead.next; } //逆序打印(利用栈的先进后出特性，不破坏原链表的结构) public static void reversePrint(Hero head) { if (head.next == null) { System.out.println("链表为空"); } Stack<Hero> stack = new Stack<>(); Hero temp = head.next; while (temp != null) { stack.push(temp); temp = temp.next; } while (stack.size() > 0) { System.out.println(stack.pop()); } } ///按顺序将两个链表合并成链表(练习) public static void jojnLinkedList(Hero head1, Hero head2) { Hero temp1 = head1.next; Hero temp2 = head2.next; Hero temp3 = null; //暂存temp1.next;若无变量暂存，后面temp1.next已经指向其他值，不是我们想要的结果。 while (temp1 ! while (temp1 != null && temp2 != null) { if(temp1.next == null){ temp1.next = temp2; break; } if (temp2.no > temp1.no && temp2.no < temp1.next.no) { head2.next = temp2.next; temp3 = temp1.next; temp1.next = temp2; temp2.next = temp3; temp1 = temp1.next; temp2 = head2.next; } else temp1 = temp1.next; } } } /* private 私有 只能在同一类中访问 friendly(默认) 可以在同一包下访问(子孙只能在同一包下) protected 保护 可以在同一包下访问(其他包的继承使用protected修饰的，其子孙也可以继承，即使是其他包的子孙也可以访问) public 公共 到处都可以访问 */ class Hero{ public int no; public String name; public String nickName; public Hero next; public Hero(int no,String name,String nickName){ this.no = no; this.name = name; this.nickName = nickName; } @Override pubic String toString() {
return "Hero{" +
"no=" + no +
", name='" + name + '\'' +
", nickName='" + nickName + '\'' +
'}';
}
}
class SingleLinked{
Hero head = new Hero(0,"","");//头结点
public Hero getHead() {
return head;
}
//直接添加在链表尾部(不考虑顺序)
public void addHero(Hero heroNode){
Hero temp = head; //因为是单链表，头结点不能动，否则会找不到链表。所以利用一个temp结点来完成操作
while(true){
if(temp.next == null){
break;
}
temp = temp.next;
}
temp.next = heroNode;
}
//按顺序添加
public void addHeroByOrder(Hero heroNode){
Hero temp = head;
while (true){
if(temp.next == null){
temp.next = heroNode;
break;
}
else if(heroNode.no < temp.next.no){
heroNode.next = temp.next;
temp.next = heroNode;
break;
}
if(heroNode.no == temp.next.no){
System.out.printf("结点%d已存在，插入失败\n",heroNode.no);
break;
}
temp = temp.next;
}
}
public void delete(Hero heroNode){
if(head.next == null){
System.out.println("链表为空");
return;
}
Hero temp = head; // temp 是等于head 还是等于 head.next 。具体需要具体分析
Boolean flag = false;
while (true){
if(temp.next == null){
break;
}
if(temp.next.no == heroNode.no){
flag = true;
break;
}
temp = temp.next;
}
if(flag){
temp.next = temp.next.next;
}
else {
System.out.println("没有你要删除的结点");
}
}
public void update(Hero heroNode){
Hero temp = head.next ;
if(temp == null){
System.out.println("链表为空，请先插入数据");
return;
}
while (true){
if(temp == null ){
System.out.println("没有该结点");
break;
}
if(temp.no == heroNode.no){
temp.name = heroNode.name;
temp.nickName = heroNode.nickName;
break;
}
temp = temp.next;
}
}
public void showHero(){
if(head.next == null){
System.out.println("链表为空");
}
Hero temp = head.next;
while (true){
if(temp == null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
}
二.双向链表
package com.bzw.linkedlist;
public class DoubleLinked {
public static void main(String[] args) {
Hero2 hero1 = new Hero2(1, "宋江", "及时雨");
Hero2 hero2 = new Hero2(2, "卢俊义", "玉麒麟");
Hero2 hero3 = new Hero2(3, "吴用", "智多星");
Hero2 hero4 = new Hero2(4, "林冲", "豹子头");
Hero2 hero5 = new Hero2(2, "小卢", "玉麒麟~~");
DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
// doubleLinkedList.add(hero1);
// doubleLinkedList.add(hero2);
// doubleLinkedList.add(hero3);
// doubleLinkedList.add(hero4);
doubleLinkedList.addByOrder(hero1);
doubleLinkedList.addByOrder(hero4);
doubleLinkedList.addByOrder(hero2);
doubleLinkedList.addByOrder(hero3);
doubleLinkedList.delete(hero3);
// doubleLinkedList.update(hero5);
// doubleLinkedList.delete(hero5);
doubleLinkedList.showLinked();
}
}
class Hero2{
public int no;
public String name;
public String nick;
public Hero2 pre;
public Hero2 next;
public Hero2(int no,String name,String nick){
this.no = no;
this.name = name;
this.nick = nick;
}
@Override
public String toString() {
return "Hero2{" +
"no=" + no +
", name='" + name + '\'' +
", nick='" + nick + '\'' +
'}';
}
}
class DoubleLinkedList{
Hero2 head = new Hero2(0,"","");
public Hero2 getHead() {
return head;
}
//遍历(不要小看任何一个操作，思路稍微有点错就达不到理想效果)
public void showLinked(){
if(head.next == null){
System.out.println("链表为空");
}
Hero2 temp = head.next;
while (true){
if(temp == null){
break;
}
System.out.println(temp);
temp = temp.next;
}
}
//添加(直接添加在最后)
public void add(Hero2 newHeroNode) {
Hero2 temp = head;
while (true) {
if (temp.next == null){
break;
}
temp = temp.next;
}
temp.next = newHeroNode;
newHeroNode.pre = temp;
}
//添加(按顺序添加)
public void addByOrder(Hero2 newHeroNode){
Hero2 temp = head;
while (true){
if (temp.next == null){
temp.next = newHeroNode;
newHeroNode.pre = temp;
break;
}
if (newHeroNode.no > temp.no && newHeroNode.no < temp.next.no ){
temp.next.pre = newHeroNode;
newHeroNode.next = temp.next;
temp.next = newHeroNode;
newHeroNode.pre = temp;
break;
}
else if (newHeroNode.no < temp.no && newHeroNode.no >temp.pre.no){
newHeroNode.pre = temp.pre;
temp.pre.next = newHeroNode;
temp.pre = newHeroNode;
newHeroNode.next = temp;
break;
}
else if (newHeroNode.no == temp.no){
System.out.println("结点已存在");
}
temp = temp.next;
}
}
//修改
public void update(Hero2 newHeroNode){
Hero2 temp = head.next;
if (temp == null){
System.out.println("空链表");
}
while (true){
if (temp.no == newHeroNode.no){
temp.name = newHeroNode.name;
temp.nick = newHeroNode.nick;
break;
}
temp = temp.next;
}
}
//删除(双向链表的删除和单链表有所不同。单链表删除时是找到要删除结点的前一个结点，
// 而双向链表就是找到要删除的这个结点。)
public void delete(Hero2 heroNode){
Hero2 temp = head.next;
while (true){
if (temp.no == heroNode.no){
temp.pre.next = temp.next;
temp.next.pre = temp.pre;
break;
}
temp = temp.next;
}
}
}
三.循环链表(约瑟夫问题)
package com.bzw.linkedlist;
//约瑟夫环实现代码
public class RingLinkedList {
public static void main(String[] args) {
RingLinked ringLinked = new RingLinked();
ringLinked.add(5);
ringLinked.show();
ringLinked.countBoy(1,2,5);
}
}
class Boy{
private int no;
private Boy next;
public Boy(int no){
this.no = no;
}
public int getNo() {
return no;
}
public void setNo(int no) {
this.no = no;
}
public Boy getNext() {
return next;
}
public void setNext(Boy next) {
this.next = next;
}
@Override
public String toString() {
return "Boy{" +
"no=" + no +
'}';
}
}
class RingLinked{
Boy first = null;
//添加(这里是实现约瑟夫环问题代码，实现环形链表可以设头结点也可以不设)
public void add(int nums) {
Boy temp = null;
for (int i = 1; i <= nums; i++) {
Boy boy = new Boy(i);
if (i == 1) {
first = boy;
first.setNext(first);
temp = first;
} else {
temp.setNext(boy);
boy.setNext(first);
temp = boy;
}
}
}
//遍历
public void show(){
if (first == null){
System.out.println("空链表");
return;
}
Boy temp = first;
while (true){
System.out.println(temp);
if (temp.getNext() == first){
break;
}
temp = temp.getNext();
}
}
//出圈顺序
public void countBoy(int k,int m,int n){
Boy helper = first;//始终跟在first后面，用于删除结点
while (true){
if (helper.getNext() == first)
break;
else {
helper = helper.getNext();//helper = helper.next;
}
}
//移动到开始报数的那个位置
for (int i=0;i<k-1;i++){
first = first.getNext();
helper = helper.getNext();
}
while (true){
//圈中只剩一个结点
if (helper == first){
break;
}
for (int i=0;i<m-1;i++){
first = first.getNext();
helper = helper.getNext();
}
System.out.println("出圈结点为：" + first.getNo());
first = first.getNext();
helper.setNext(first);//helper.next = first;
}
System.out.println("最后一个结点为："+helper.getNo());
}
}