链表

链表

1 链表

• 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。
  

2 单链表

• 商品结点类
  

1. package com.acti.linkedList;
3. /**
4. * author hongyeci
5. * date 20220722
6. * version 1.0
7. * remark 单链表--商品类
8. */
9. public class GoodsNode {
10.     private int goodsId;
11.     private String goodsName;
12.     private double goodsPrice;
13.     private GoodsNode next;
15.     public GoodsNode() {
16.     }
18.     public GoodsNode(int goodsId, String goodsName, double goodsPrice) {
19.         this.goodsId = goodsId;
20.         this.goodsName = goodsName;
21.         this.goodsPrice = goodsPrice;
22.     }
24.     public int getGoodsId() {
25.         return goodsId;
26.     }
28.     public void setGoodsId(int goodsId) {
29.         this.goodsId = goodsId;
30.     }
32.     public String getGoodsName() {
33.         return goodsName;
34.     }
36.     public void setGoodsName(String goodsName) {
37.         this.goodsName = goodsName;
38.     }
40.     public double getGoodsPrice() {
41.         return goodsPrice;
42.     }
44.     public void setGoodsPrice(double goodsPrice) {
45.         this.goodsPrice = goodsPrice;
46.     }
48.     public GoodsNode getNext() {
49.         return next;
50.     }
52.     public void setNext(GoodsNode next) {
53.         this.next = next;
54.     }
56.     @Override
57.     public String toString() {
58.         return "GoodsNode{" +
59.                 "goodsId=" + goodsId +
60.                 ", goodsName='" + goodsName + '\'' +
61.                 ", goodsPrice=" + goodsPrice +
62.                 ", next=" + next +
63.                 '}';
64.     }
65. }

复制代码

• 带有头结点的单链表
  

1. package com.acti.linkedList;
4. /**
5. * author hongyeci
6. * date 20220722
7. * version 1.0
8. * remark 带有头结点的单链表
9. */
10. public class SingleLinkedList {
11.     private GoodsNode node = new GoodsNode(0,"头结点",0.0);
13.     /**
14.      * 增加结点-添加到末尾结点
15.      * @param goodsNode 商品结点
16.      */
17.     public void addNode(GoodsNode goodsNode){
18.         GoodsNode temp = node;
19.         while(true){
20.             if (temp.getNext() == null){
21.                 break;
22.             }
23.             temp=temp.getNext();
24.         }
25.         temp.setNext(goodsNode);
26.     }
28.     /**
29.      * 指定位置插入值
30.      * 按照商品id值顺序插入到链表中
31.      * @param goodsNode
32.      */
33.     public void insertNode(GoodsNode goodsNode){
34.         GoodsNode temp = node;
35.         boolean flag = false;
36.         while(true){
37.             if (temp.getNext() == null){
38.                 break;
39.             }
40.             if (temp.getNext().getGoodsId()>goodsNode.getGoodsId()){
41.                 break;
42.             }else if (temp.getNext().getGoodsId() == goodsNode.getGoodsId()){
43.                 flag = true;
44.                 break;
45.             }
46.             temp=temp.getNext();
47.         }
48.         if (flag){
49.             throw new RuntimeException("不能插入重复的商品...");
50.         }else {
51.             goodsNode.setNext(temp.getNext());
52.             temp.setNext(goodsNode);
53.         }
54.     }
56.     /**
57.      * 修改指定结点data域信息
58.      * @param goodsNode
59.      */
60.     public void updateNode(GoodsNode goodsNode){
61.         GoodsNode temp = node;
62.         if (temp.getNext() == null){
63.             throw new RuntimeException("该链表为空链表，不能进行修改操作...");
64.         }
65.         boolean flag = false;
66.         while (true){
67.             //1 直到最后一个结点
68.             if (temp.getNext()==null){
69.                 break;
70.             }
71.             //2 找到指定结点
72.             if (temp.getNext().getGoodsId()==goodsNode.getGoodsId()){
73.                 flag = true;
74.                 break;
75.             }
76.             temp = temp.getNext();
77.         }
78.         if (flag){
79.             //修改指定结点data域数据
80.             temp.getNext().setGoodsName(goodsNode.getGoodsName());
81.             temp.getNext().setGoodsPrice(goodsNode.getGoodsPrice());
82.         }else {
83.             throw new RuntimeException("未找到指定结点...");
84.         }
85.     }
87.     /**
88.      * 删除指定结点
89.      * 根据结点ID删除指定结点
90.      * @param goodsId
91.      */
92.     public void deleteNode(int goodsId){
93.         //判断链表是否为空
94.         if (node.getNext() == null){
95.             throw new RuntimeException("该链表为空链表，不能进行删除操作...");
96.         }
97.         GoodsNode temp = node;  //头结点
98.         boolean flag = false;   //是否做删除操作标识
99.         //遍历链表结点 获取指定结点
100.         while (true){
101.             //遍历至最后一个结点 退出遍历
102.             if (temp.getNext()==null){
103.                 break;
104.             }
105.             //找到指定结点
106.             if (temp.getNext().getGoodsId()==goodsId){
107.                 flag = true;
108.                 break;
109.             }
110.             temp = temp.getNext();
111.         }
112.         if (flag){
113.             //删除操作
114.             temp.setNext(temp.getNext().getNext());
115.         }else {
116.             throw new RuntimeException("未找到指定删除结点...");
117.         }
118.     }
121.     /**
122.      * 获取当前单链表的结点个数
123.      * @return
124.      */
125.     public int lengthNode(){
126.         int length = 0;
127.         GoodsNode temp = node.getNext();
128.         while (temp!=null){
129.             length++;
130.             temp = temp.getNext();
131.         }
132.         return length;
133.     }
135.     /**
136.      * 查看链表元素
137.      */
138.     public void listNode(){
139.         if (node.getNext()==null){
140.             System.out.println("空链表...");
141.         }else {
142.             GoodsNode temp = node;
143.             while (true){
144.                 if (temp.getNext()==null){
145.                     break;
146.                 }
147.                 temp = temp.getNext();
148.                 System.out.println(temp);
149.             }
150.         }
151.     }
153. }

复制代码

3 双链表

• 图书结点类
  

1. package com.acti.linkedList;
3. /**
4. * author hongyeci
5. * date 20220725
6. * version 1.0
7. * remark 双链表--图书类
8. */
9. public class BooksNode {
10.     private int id;
11.     private String name;
12.     private double price;
13.     private BooksNode pre; //双链表前驱结点
14.     private BooksNode next; //双链表后继结点
16.     public BooksNode() {
17.     }
19.     public BooksNode(int id, String name, double price) {
20.         this.id = id;
21.         this.name = name;
22.         this.price = price;
23.     }
25.     public int getId() {
26.         return id;
27.     }
29.     public void setId(int id) {
30.         this.id = id;
31.     }
33.     public String getName() {
34.         return name;
35.     }
37.     public void setName(String name) {
38.         this.name = name;
39.     }
41.     public double getPrice() {
42.         return price;
43.     }
45.     public void setPrice(double price) {
46.         this.price = price;
47.     }
49.     public BooksNode getPre() {
50.         return pre;
51.     }
53.     public void setPre(BooksNode pre) {
54.         this.pre = pre;
55.     }
57.     public BooksNode getNext() {
58.         return next;
59.     }
61.     public void setNext(BooksNode next) {
62.         this.next = next;
63.     }
65.     @Override
66.     public String toString() {
67.         return "BooksNode{" +
68.                 "id=" + id +
69.                 ", name='" + name + '\'' +
70.                 ", price=" + price +
71.                 '}';
72.     }
73. }

复制代码

• 带有头结点的双链表
  

1. package com.acti.linkedList;
3. /**
4. * author hongyeci
5. * date 20220725
6. * version 1.0
7. * remark 带有头结点的双链表
8. */
9. public class DoubleLinkedList {
10.     private BooksNode head = new BooksNode(0,"头结点",0.0);
12.     /**
13.      * 增加结点-添加到末尾结点
14.      * @param booksNode 图书结点
15.      */
16.     public void addNode(BooksNode booksNode){
17.         BooksNode temp = head;
18.         while(true){
19.             if (temp.getNext() == null){
20.                 break;
21.             }
22.             temp=temp.getNext();
23.         }
24.         temp.setNext(booksNode);
25.         booksNode.setPre(temp);
26.     }
28.     /**
29.      * 指定位置插入值
30.      * 按照商品id值顺序插入到链表中
31.      * @param booksNode
32.      */
33.     public void insertNode(BooksNode booksNode){
34.         BooksNode temp = head;
35.         boolean flag = false;
36.         while(true){
37.             if (temp.getNext() == null){
38.                 break;
39.             }
40.             if (temp.getNext().getId()>booksNode.getId()){
41.                 break;
42.             }else if (temp.getId() == booksNode.getId()){
43.                 flag = true;
44.                 break;
45.             }
46.             temp=temp.getNext();
47.         }
48.         if (flag){
49.             throw new RuntimeException("不能插入重复的商品...");
50.         }else {
51.             if (temp.getNext()==null){
52.                 temp.setNext(booksNode);
53.                 booksNode.setPre(temp);
54.             }else {
55.                 //1、当前结点的后继结点后继节点前驱指向新结点
56.                 temp.getNext().setPre(booksNode);
57.                 //2、新结点后继结点指向当前结点后继结点
58.                 booksNode.setNext(temp.getNext());
59.                 //3、新结点前驱结点指向当前结点
60.                 booksNode.setPre(temp);
61.                 //4、当前结点后继结点指向新结点
62.                 temp.setNext(booksNode);
63.             }
65.         }
66.     }
68.     /**
69.      * 修改指定结点data域信息
70.      * @param booksNode
71.      */
72.     public void updateNode(BooksNode booksNode){
73.         BooksNode temp = head;
74.         if (temp.getNext() == null){
75.             throw new RuntimeException("该双向链表为空链表，不能进行修改操作...");
76.         }
77.         boolean flag = false;
78.         while (true){
79.             //1 直到最后一个结点
80.             if (temp.getNext()==null){
81.                 break;
82.             }
83.             //2 找到指定结点
84.             if (temp.getId()==booksNode.getId()){
85.                 flag = true;
86.                 break;
87.             }
88.             temp = temp.getNext();
89.         }
90.         if (flag){
91.             //修改指定结点data域数据
92.             temp.setName(booksNode.getName());
93.             temp.setPrice(booksNode.getPrice());
94.         }else {
95.             throw new RuntimeException("未找到指定结点...");
96.         }
97.     }
99.     /**
100.      * 删除指定结点
101.      * 根据结点ID删除指定结点
102.      * @param id
103.      */
104.     public void deleteNode(int id){
105.         BooksNode temp = head;  //头结点
106.         //判断链表是否为空
107.         if (temp.getNext() == null){
108.             throw new RuntimeException("该链表为空链表，不能进行删除操作...");
109.         }
110.         boolean flag = false;   //是否做删除操作标识
111.         //遍历链表结点 获取指定结点
112.         while (true){
113.             //遍历至最后一个结点 退出遍历
114.             if (temp.getNext()==null){
115.                 break;
116.             }
117.             //找到指定结点
118.             if (temp.getId()==id){
119.                 flag = true;
120.                 break;
121.             }
122.             temp = temp.getNext();
123.         }
124.         if (flag){
125.             //1、当前结点前驱结点的后继指向当前结点的后继结点
126.             temp.getPre().setNext(temp.getNext());
127.             //2、当前结点的后继结点前驱指向当前结点的前驱结点
128.             if (temp.getNext()!=null){
129.                 temp.getNext().setPre(temp.getPre());
130.             }
131.         }else {
132.             throw new RuntimeException("未找到指定删除结点...");
133.         }
134.     }
137.     /**
138.      * 获取当前单链表的结点个数
139.      * @return
140.      */
141.     public int lengthNode(){
142.         int length = 0;
143.         BooksNode temp = head.getNext();
144.         while (temp!=null){
145.             length++;
146.             temp = temp.getNext();
147.         }
148.         return length;
149.     }
151.     /**
152.      * 查看链表元素
153.      */
154.     public void listNode(){
155.         if (head.getNext()==null){
156.             System.out.println("空链表...");
157.         }else {
158.             BooksNode temp = head;
159.             while (true){
160.                 if (temp.getNext()==null){
161.                     break;
162.                 }
163.                 temp = temp.getNext();
164.                 System.out.println(temp);
165.             }
166.         }
167.     }
169. }

复制代码

4 单向环形链表-约瑟夫环

<ul>设编号为1,2,...,n的n个人围坐成一圈，约定编号为k(1=