【数据结构】链表_链表数据结构

一、链表的定义及特点

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

链表通常是由一串节点（链节点）组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个或下一个节点的位置链接（links）也就是数据的地址（指针）。

图解：

head为头节点，不存放任何数据，只存放指向链表中真正存放数据的第一个节点的地址，充当指针。

特点：

• 使用链表结构可以克服数组需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理（用一个空间就加一个，没有浪费多余的空间）。但是链表失去了数组随机读取的优点，同时链表由于增加了节点的指针域，空间开销比较大。
• 链表是一种插入和删除都比较快的数据结构，缺点是查找比较慢。除非需要频繁的通过下标来随机访问数据，否则在很多使用数组的地方都可以用链表代替。

二、链表的分类

从实现方式可以分为单向链表、双向链表、循环链表。

单向链表：指的是链表中的节点指向只能指向下一个节点或者为空，节点之间不能相互指向。

双向链表：链表中，每个链表节点既有指向下一个节点的指针，又有指向前一个节点的指针，即每个节点都有两种指针。

循环链表：指的是在单向链表和双向链表的基础上，将两种链表的最后一个节点指向第一个节点从而实现循环。（双向链表中第一个节点中存在指向最后一个节点的指针）。

三、Java中链表的基本操作示例

1.定义一个简单的类用来保存节点关系，并将所有节点链接起来。

/**
 * @author Xin
 * @date 2022/9/30
 */

class Node {
    private String data; //用于保存数据
    private Node next;   //用于保存下一个节点

    public Node(String data){ //每个Node类对象都必须保存有数据
        this.data = data;
    }

    public String getData() {
        return this.data;
    }

    public Node getNext() {
        return this.next;
    }

    public void setNext(Node next) {
        this.next = next;
    }
}

public class LinkedList {
    public static void main(String[] args) {
        //准备数据
        Node head = new Node("火车头");
        Node n1 = new Node("车厢1");
        Node n2 = new Node("车厢2");

        //连接节点
        head.setNext(n1);
        n1.setNext(n2);

        //取出所有数据
        Node currentNode = head; //从当前根节点开始读取
        while (currentNode != null){
            System.out.println(currentNode.getData());
            //将下一个节点设为当前节点，以便循环的继续
            currentNode = currentNode.getNext();
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

运行结果：

2.在进行链表操作的时候，首先需要的是一个根节点（第一个节点即为根节点），之后每一个节点的引用都保存在上一节点的next属性之中，而在进行输出的时候也应该按照节点的先后顺序，一个一个取得每一个节点所包装的数据。

/**
 * @author Xin
 * @date 2022/9/30
 */

public class LinkedList1 {

    public static void main(String[] args) {
        Link link = new Link() ;
        System.out.println("link1++++++++++++"+link);
        link.add("hello");   //增加节点
        System.out.println("link2++++++++++++"+link);
        link.add("world");
        System.out.println("link3++++++++++++"+link);
        link.add("wwww");
        System.out.println("link4++++++++++++"+link);
        link.print();     //打印数据
    }
}

//每一个链表实际上就是由多个节点组成的
class Node2 {
    private String data; // 用于保存数据
    private Node2 next; // 用于保存下一个节点

    public Node2(String data) {  // 每一个Node类对象都必须保存有响应的数据
        this.data = data;
    }

    public void setNext(Node2 next) {
        this.next = next;
    }

    public Node2 getNext() {
        return this.next;
    }

    public String getData() {
        return this.data;
    }

    // 实现节点的添加:
    // 第一次调用（Link）：this代表Link.root
    // 第二次调用（Node2）：this代表Link.root.next
    // 第三次调用（Node2）：this代表Link.root.next.next
    public void addNode(Node2 oldNode,Node2 newNode) {
        System.out.println("now:"+oldNode);
        if (this.next == null) {   // 保存新节点
            this.next = newNode;
        } else {                 // 当前节点后面还有节点
            this.next.addNode(this.next,newNode);  // 当前节点的下一个节点继续保存,这里采用的是递归添加节点
        }
        System.out.println(oldNode+"=>"+this.next);
    }

    // 第一次调用（Link）：this代表Link.root
    // 第二次调用（Node）：this代表Link.root.next
    // 第三次调用（Node）：this代表Link.root.next.next
    public void printNode() {
        System.out.println("pp:"+this.data);// 输出当前数据
        if (this.next != null) {      // 如果还有下一个节点，输出下一节点
            this.next.printNode();   // 递归打印节点，注意这里的this.next中的this指代
        }
    }
}


// 链表增加节点，输出节点数据
class Link {

    private Node2 root; //新建根节点

    public void add (String data){
        Node2 newNode = new Node2(data);  //链表中新增节点类对象
        System.out.println("0:===="+newNode);
        if(this.root == null ){         // 如果链表还没有任何节点,就添加第一个节点作为根节点
            this.root = newNode;
            System.out.println("1:root:===="+this.root);
        }else{
            System.out.println("2:new:===="+newNode);
            this.root.addNode(this.root,newNode);  //从根节点节点新链接一个节点
        }
    }

    //输出当前节点数据
    public void print(){
        if( this.root != null ){
            this.root.printNode();
        }
    }

}


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94

运行结果：

3.构造一个类，里面包含一个指向下一个元素的对象（指向下一个元素的指针）

/**
 * @author Xin
 * @date 2022/9/30
 */

public class LinkedList2 {
    public static void main(String[] args) {
        MyLinkedList linkedList = new MyLinkedList();
        System.out.println("-------start-------");
        System.out.println("ll:"+linkedList.listEm());

        for (int i=0;i<5;i++){   //新建链表
            linkedList.add(i+1);
        }
        System.out.println("mm:"+linkedList.listEm());  //打印链表

        for(int i=0;i<5;i++){  //删除链表
            System.out.println("remove:"+linkedList.remove());
        }
        System.out.println("kk:"+linkedList.listEm());
        System.out.println("-------end-------");
    }
}

class Node1<T> {
    Node1<T> next;
    T element;
    public Node1( Node1<T> next, T element){
        this.next = next;
        this.element = element;
    }
}

class MyLinkedList<T> {

    private int size ;
    Node1<T> last;     //指向list中最后一个元素
    Node1<T> first;    //指向list中第一个元素
    Node1<T> currRead; //指向当前读取的元素

    // 默认构造函数
    public MyLinkedList(){
        this.size = 0;
        this.last =  new Node1(null,-1);
        this.first = last;
        this.currRead = first;
    }

    //往链表中添加数据（队尾添加数据）
    public void add(T element){
        Node1<T> newNode = new Node1<T>(null,element);
        this.last.next = newNode;
        this.last = newNode;  // 引用平移
        if(size == 0){
            this.first = newNode;
        }
        size ++;

    }

    //移除链表中的数据（队头移除）
    public T remove(){
        if(size == 0){
            System.out.println("empty list ");
            this.currRead = this.first;
            return null;
        }
        T result = this.first.element;
        this.first = this.first.next;
        this.currRead = this.first;
        size--;
        return result;
    }

    //获取队列中的元素
    public T get(){
        if(this.currRead.next == null){
            this.setReadAgain();
            return this.currRead.element;
        }
        T result = this.currRead.element;
        this.currRead = this.currRead.next;
        return result;
    }

    //再次从头开始读取数据
    public void setReadAgain() {
        this.currRead = this.first;
    }

    public String listEm(){
        StringBuilder sb = new StringBuilder();
        for(int i=0;i<size;i++){
            T ele = this.get();
            sb.append(this.currRead.element + "-->");
        }
        return sb.toString();
    }

    //获取队列大小
    public int getSize(){
        return this.size;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

运行结果：

4.例四

/**
 * @author Xin
 * @date 2022/9/30
 */

public class LinkedList3 {
    public static void main(String [] args){

        Link1 l=new Link1();
        mytype[] la;
        mytype dsome=new mytype("韩敏","dsome",21);
        mytype shao=new mytype("邵晓","john",45);
        mytype hua=new mytype("华晓风","jam",46);
        mytype duo=new mytype("余小风","duo",1000);
        mytype wang=new mytype("王秋","jack",21);
        mytype shi=new mytype("韩寒","bob",3000);
        mytype yu=new mytype("于冬","keven",30);

        l.add(dsome);//测试增加节点
        l.add(shao);
        l.add(hua);
        l.add(wang);
        l.add(shi);
        l.add(duo);
        l.add(yu);

        System.out.println("链表长度："+l.length());//链表长度

        la=l.toArray();
        for(int i=0;i<la.length;i++){
            System.out.println(la[i].getInfo());
        }

        System.out.println("是否包含余小风:"+l.contains(duo)+"\n");
        System.out.println("删除余小风后\n");
        l.remove(duo);
        la=l.toArray();
        for(int i=0;i<la.length;i++){    //转化为数组之后输出
            System.out.println(la[i].getInfo());
        }

        System.out.println("\n利用索引方法输出全部数据");
        for(int i=0;i<l.length();i++){
            System.out.println(l.get(i).getInfo());
        }
        System.out.println("是否包含余小风:"+l.contains(duo)+"\n");
        l.clean();
        System.out.println("执行清空操作后链表长度: "+l.length()+"\t是否为空链表："+l.isEmpty());
    }
}

class Link1 {

    //内部类
    private class Node3{

        private Node3 next;
        private mytype data;

        public Node3(mytype data){
            this.data=data;
        }

        public void addNode(Node3 newNode){  //增加节点
            if(this.next==null){
                this.next=newNode;   // 指向新的节点
            }else{
                this.next.addNode(newNode);    // 递归调用是为了让next引用指向新的节点
            }
        }

        public mytype getNode(int index){//按照角标返回数据

            if(index==Link1.this.foot++){
                return this.data;
            }else{
                return this.next.getNode(index);
            }
        }

        public boolean iscontain(mytype data){//判断是否含有该数据
            if(this.data.equals(data)){
                return true;
            }else{
                if(this.next!=null){
                    return this.next.iscontain(data);
                }else{
                    return false;
                }
            }
        }

        public void removeNode(Node3 previous,mytype data){  //删除节点
            if(this.data.equals(data)){    //this：下一个节点B
                previous.next=this.next;    // this.next:节点B的下一个节点C，previous：节点A

            }else{
                this.next.removeNode(this,data);  //注意这里的this.next和this的区别：this.next是下一个节点B，this是当前节点A
            }
        }

        public void toArrayNode(){  //转化数组
            Link1.this.Larray[Link1.this.foot ++]=this.data;  //每个节点的数据添加到一个mytype []中
            if(this.next!=null){
                this.next.toArrayNode();
            }
        }
    }

    //内部类定义完毕
    private Node3 root;
    private int count=0;
    private int foot;
    private mytype [] Larray;

    public void add(mytype data){   //增加节点
        if(data==null){
            System.out.print("增加数据失败，数据为空");//测试用
            return;
        }

        Node3 newNode=new Node3(data);  //新建节点

        if(this.root==null){
            this.root=newNode;
            this.count++;
        }else{
            this.root.addNode(newNode);
            this.count++;
        }
    }

    public int length(){//链表长度
        return this.count;
    }

    public boolean isEmpty(){//是否为空链表
        if(this.count==0)return true;
        else return false;
    }

    public void clean(){//清空链表
        this.root=null;
        this.count=0;
    }

    public mytype get(int index){//索引返回节点所存的数据
        if(index>=this.count||index<0){
            System.out.print("越界错误");//测试用
            return null;
        }else{
            this.foot=0;
            return this.root.getNode(index);
        }
    }

    public boolean contains(mytype data){  //判断链表数据是否含data
        if(data==null)
            return false;
        else
            return this.root.iscontain(data);
    }

    public void remove(mytype data){  //删除指定数据节点
        if(this.contains(data)){
            if(this.root.data.equals(data)){
                this.root=this.root.next;
                this.count--;
            }
            else{
                this.count--;
                this.root.next.removeNode(root,data);
            }
        }else{
            System.out.print("删除错误");//测试用
        }
    }

    public mytype[] toArray(){  //把链表转化成对象数组
        if(this.count==0){
            return null;
        }
        this.foot=0;
        this.Larray=new mytype [this.count];
        this.root.toArrayNode();
        return this.Larray;
    }
}

class mytype {

    private String name;
    private String people;
    private int age;

    public mytype(String name,String people,int age){//链表中的数据（可自定义）
        this.name=name;
        this.people=people;
        this.age=age;
    }

    public boolean equals(mytype data){//判断数据是否相同
        if(this==data){
            return true;
        }
        if(data==null){
            return false;
        }
        if(this.name.equals(data.name)&&this.people.equals(data.people)&&this.age==data.age){
            return true;
        }else{
            return false;
        }
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public String getPeople() {
        return people;
    }

    public void setPeople(String people) {
        this.people = people;
    }

    public int getAge() {
        return age;
    }

    public void setAge(int age) {
        this.age = age;
    }

    public String getInfo(){
        return "名字 :"+this.name+"\n"+
                "人物 :"+this.people+"\n"+
                "年龄 :"+this.age;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245

运行结果：

链表长度：7
名字 :韩敏
人物 :dsome
年龄 :21
名字 :邵晓
人物 :john
年龄 :45
名字 :华晓风
人物 :jam
年龄 :46
名字 :王秋
人物 :jack
年龄 :21
名字 :韩寒
人物 :bob
年龄 :3000
名字 :余小风
人物 :duo
年龄 :1000
名字 :于冬
人物 :keven
年龄 :30
是否包含余小风:true

删除余小风后

名字 :韩敏
人物 :dsome
年龄 :21
名字 :邵晓
人物 :john
年龄 :45
名字 :华晓风
人物 :jam
年龄 :46
名字 :王秋
人物 :jack
年龄 :21
名字 :韩寒
人物 :bob
年龄 :3000
名字 :于冬
人物 :keven
年龄 :30

利用索引方法输出全部数据
名字 :韩敏
人物 :dsome
年龄 :21
名字 :邵晓
人物 :john
年龄 :45
名字 :华晓风
人物 :jam
年龄 :46
名字 :王秋
人物 :jack
年龄 :21
名字 :韩寒
人物 :bob
年龄 :3000
名字 :于冬
人物 :keven
年龄 :30
是否包含余小风:false

执行清空操作后链表长度: 0	是否为空链表：true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67