数据结构之链表

时间：2019-08-28 09:38:40 阅读：84 评论：0 收藏：0 [点我收藏+]

1.链表是以节点的方式来存储的

2.每个节点包含data域，next域，next域指向下一节点

3.链表的各个节点不一定是连续存储的(内存中不一定是连续存储的，但是我们为了学习，通常树上画出来的是有顺序的）

技术分享图片

4.链表分为带头节点的链表和不带头节点的链表

头节点不存放数据，它只用来表示单链表的头

单链表的创建,显示

　创建：1，先创建头节点，作用是表示单链表的头

　　　　 2.后面每添加一个节点，就直接加入到链表的最后，需要用一个辅助指针

　遍历：通过一个辅助指针，帮助遍历整个单链表

下面是一个添加梁山好汉的例子：

 1 package Queue.linkedlist;
 2 
 3 public class SingleLinkedList{
 4     public static void main(String[] args) {
 5         //测试
 6         //创建节点
 7         HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
 8         HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
 9         HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
10 
11         //创建单链表
12         SingleLinkedListTest test = new SingleLinkedListTest();
13         test.addHeroNode(heroNode);
14         test.addHeroNode(heroNode1);
15         test.addHeroNode(heroNode2);
16 
17         test.list();
18     }
19 }
20 
21 class SingleLinkedListTest{
22     //初始化头节点,不存放数据
23     HeroNode head = new HeroNode(0,"","");
24     //添加节点,需要传入节点
25     public void addHeroNode(HeroNode heroNode){
26         //用一个辅助指针指向头节点
27         HeroNode temp = head;
28         //遍历链表
29         while (true){
30             //如果头节点指向的下一个为空，就是空链表
31             if (temp.next == null){
32                 break;
33             }
34             //让辅助指针指向下一个链表
35             temp = temp.next;
36         }
37         //当退出while循环时，temp指向链表的最后，然后将temp指向新的节点就ok
38         temp.next = heroNode;
39     }
40     //遍历链表
41     public void  list(){
42         //判断链表是否为空
43         if (head.next == null){
44             System.out.println("链表为空");
45             return;
46         }
47         //用一个辅助指针来试探，如果指针指向的下一个节点不为空，指针后移，如果为空，则试探到了尾节点
48         HeroNode temp = head.next;
49         while (true){
50             if (temp == null){
51                 break;
52             }
53             //输出节点信息
54             System.out.println(temp);
55             //将指针temp后移
56             temp = temp.next;
57         }
58     }
59 }
60 
61 //节点
62 class HeroNode{
63     int no;//编号
64     String name;//名字
65     String nickName;//昵称
66     HeroNode next;//下一个节点
67 
68     public HeroNode(int no , String name,String nickName){
69         this.no = no;
70         this.name = name;
71         this.nickName = nickName;
72     }
73 
74     @Override
75     public String toString() {
76         return "HeroNode{" +
77                 "no=" + no +
78                 ", name=‘" + name + ‘\‘‘ +
79                 ", nickName=‘" + nickName + ‘\‘‘ +
80                 ‘}‘;
81     }
82 }

View Code

但是上述添加没有添加到指定的位置

按照顺序添加

　　1，首先找到新添加的节点的位置（应该放在什么地方的位置，通过辅助指针）

　　2.新的节点.next = temp.next

技术分享图片

　　3.将temp.next = 新的节点

  1 package Queue.linkedlist;
  2 
  3 public class SingleLinkedList{
  4     public static void main(String[] args) {
  5         //测试
  6         //创建节点
  7         HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
  8         HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
  9         HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
 10 
 11         //创建单链表
 12         SingleLinkedListTest test = new SingleLinkedListTest();
 13         test.addByOrder(heroNode);
 14         test.addByOrder(heroNode2);
 15         test.addByOrder(heroNode1);
 16 
 17         test.list();
 18 
 19     }
 20 }
 21 
 22 class SingleLinkedListTest{
 23     //初始化头节点,不存放数据
 24     HeroNode head = new HeroNode(0,"","");
 25     //添加节点,需要传入节点
 26     public void addHeroNode(HeroNode heroNode){
 27         //用一个辅助指针指向头节点
 28         HeroNode temp = head;
 29         //遍历链表
 30         while (true){
 31             //如果头节点指向的下一个为空，就是空链表
 32             if (temp.next == null){
 33                 break;
 34             }
 35             //让辅助指针指向下一个链表
 36             temp = temp.next;
 37         }
 38         //当退出while循环时，temp指向链表的最后，然后将temp指向新的节点就ok
 39         temp.next = heroNode;
 40     }
 41 
 42     //按顺序添加
 43     public void addByOrder(HeroNode heroNode){
 44         HeroNode temp = head;
 45         boolean flag = false;//标志编号是否存在
 46         while (true){
 47             if (temp.next== null){
 48                 break;
 49             }
 50             if (temp.next.no > heroNode.no){//找到位置
 51                 break;
 52             }
 53             else if (temp.next.no == heroNode.no){
 54                 flag = true;
 55             }
 56             temp = temp.next;
 57         }
 58         if (flag){
 59             System.out.println("插入的编号已经存在");
 60         }
 61         else {
 62             //插入到temp后面
 63             heroNode.next = temp.next;
 64             temp.next = heroNode;
 65         }
 66 
 67     }
 68     //遍历链表
 69     public void  list(){
 70         //判断链表是否为空
 71         if (head.next == null){
 72             System.out.println("链表为空");
 73             return;
 74         }
 75         //用一个辅助指针来试探，如果指针指向的下一个节点不为空，指针后移，如果为空，则试探到了尾节点
 76         HeroNode temp = head.next;
 77         while (true){
 78             if (temp == null){
 79                 break;
 80             }
 81             //输出节点信息
 82             System.out.println(temp);
 83             //将指针temp后移
 84             temp = temp.next;
 85         }
 86     }
 87 }
 88 
 89 //节点
 90 class HeroNode{
 91     int no;//编号
 92     String name;//名字
 93     String nickName;//昵称
 94     HeroNode next;//下一个节点
 95 
 96     public HeroNode(int no , String name,String nickName){
 97         this.no = no;
 98         this.name = name;
 99         this.nickName = nickName;
100     }
101 
102     @Override
103     public String toString() {
104         return "HeroNode{" +
105                 "no=" + no +
106                 ", name=‘" + name + ‘\‘‘ +
107                 ", nickName=‘" + nickName + ‘\‘‘ +
108                 ‘}‘;
109     }
110 }

View Code

单链表修改节点：

  1 package Queue.linkedlist;
  2 
  3 public class SingleLinkedList{
  4     public static void main(String[] args) {
  5         //测试
  6         //创建节点
  7         HeroNode heroNode = new HeroNode(1,"宋江","及时雨");
  8         HeroNode heroNode1 = new HeroNode(2,"卢俊义","玉麒麟");
  9         HeroNode heroNode2 = new HeroNode(3,"无用","智多星");
 10 
 11         //创建单链表
 12         SingleLinkedListTest test = new SingleLinkedListTest();
 13 //        test.addHeroNode(heroNode);
 14 //        test.addHeroNode(heroNode2);
 15 //        test.addHeroNode(heroNode1);
 16 
 17         test.addByOrder(heroNode);
 18         test.addByOrder(heroNode2);
 19         test.addByOrder(heroNode1);
 20 
 21         test.list();
 22         //测试修改
 23         HeroNode newHeroNode = new HeroNode(2,"卢俊义","小义");
 24         test.update(newHeroNode);
 25 
 26         test.list();
 27 
 28     }
 29 }
 30 
 31 class SingleLinkedListTest{
 32     //初始化头节点,不存放数据
 33     HeroNode head = new HeroNode(0,"","");
 34     //添加节点,需要传入节点
 35     public void addHeroNode(HeroNode heroNode){
 36         //用一个辅助指针指向头节点
 37         HeroNode temp = head;
 38         //遍历链表
 39         while (true){
 40             //如果头节点指向的下一个为空，就是空链表
 41             if (temp.next == null){
 42                 break;
 43             }
 44             //让辅助指针指向下一个链表
 45             temp = temp.next;
 46         }
 47         //当退出while循环时，temp指向链表的最后，然后将temp指向新的节点就ok
 48         temp.next = heroNode;
 49     }
 50 
 51     //按顺序添加
 52     public void addByOrder(HeroNode heroNode){
 53         HeroNode temp = head;
 54         boolean flag = false;//标志编号是否存在
 55         while (true){
 56             if (temp.next== null){
 57                 break;
 58             }
 59             if (temp.next.no > heroNode.no){//找到位置
 60                 break;
 61             }
 62             else if (temp.next.no == heroNode.no){
 63                 flag = true;
 64             }
 65             temp = temp.next;
 66         }
 67         if (flag){
 68             System.out.println("插入的编号已经存在");
 69         }
 70         else {
 71             //插入到temp后面
 72             heroNode.next = temp.next;
 73             temp.next = heroNode;
 74         }
 75 
 76     }
 77 
 78     //修改节点信息，根据和编号no,no不能修改
 79     public void update(HeroNode newHeroNode){
 80         //判空
 81         if (head.next == null){
 82             System.out.println("链表为空");
 83             return;
 84         }
 85         //辅助指针
 86         HeroNode temp = head.next;
 87         boolean flag = false;
 88         while (true){
 89             if (temp == null){
 90                 break;//遍历完了
 91             }
 92             if (temp.no == newHeroNode.no){
 93                 flag = true;//找到
 94                 break;
 95             }
 96             //继续遍历
 97             temp = temp.next;
 98         }
 99         if (flag){
100             temp.name = newHeroNode.name;
101             temp.nickName = newHeroNode.nickName;
102         }
103         else {
104             //没找到
105             System.out.println("没有找到修改的编号");
106         }
107     }
108     //遍历链表
109     public void  list(){
110         //判断链表是否为空
111         if (head.next == null){
112             System.out.println("链表为空");
113             return;
114         }
115         //用一个辅助指针来试探，如果指针指向的下一个节点不为空，指针后移，如果为空，则试探到了尾节点
116         HeroNode temp = head.next;
117         while (true){
118             if (temp == null){
119                 break;
120             }
121             //输出节点信息
122             System.out.println(temp);
123             //将指针temp后移
124             temp = temp.next;
125         }
126     }
127 }
128 
129 //节点
130 class HeroNode{
131     int no;//编号
132     String name;//名字
133     String nickName;//昵称
134     HeroNode next;//下一个节点
135 
136     public HeroNode(int no , String name,String nickName){
137         this.no = no;
138         this.name = name;
139         this.nickName = nickName;
140     }
141 
142     @Override
143     public String toString() {
144         return "HeroNode{" +
145                 "no=" + no +
146                 ", name=‘" + name + ‘\‘‘ +
147                 ", nickName=‘" + nickName + ‘\‘‘ +
148                 ‘}‘;
149     }
150 }

View Code

数据结构之链表

原文：https://www.cnblogs.com/steakliu/p/11421608.html

踩

(0)

评论一句话评论（0）

分享档案

更多>

2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)