[Collection与数据结构] 链表与LinkedList(四):双向无头非循环链表的实现与LinkedList的使用

作者：AllinToyou | 2024-04-28 21:56:22

踩

1. 双向无头非循环链表的实现

在这里插入图片描述
下面我们给出一个接口,接口中的这些方法就是待实现的方法

public interface ILinkedList_2 {
        //头插法
      void addFirst(int data);
        //尾插法
      void addLast(int data);
        //任意位置插入,第一个数据节点为0号下标
      void addIndex(int index,int data);
        //查找是否包含关键字key是否在单链表当中
      boolean contains(int key);
        //删除第一次出现关键字为key的节点
      void remove(int key);
        //删除所有值为key的节点
      void removeAllKey(int key);
        //得到单链表的长度
      int size();
      void display();
      void clear();
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

下面实现这些方法:

/**
 * 双向链表的实现
 */
public class MyLinkedList_2 implements ILinkedList_2 {
    class ListNode{
        public ListNode pre;//比单向链表多出来的地方,和前一个结点也是连起来的
        public ListNode next;
        public int val;

        public ListNode(int val) {
            this.val = val;
        }
    }
    public ListNode head;
    public ListNode last;//有末结点

    /**
     * 头插法
     * @param data
     */
    @Override
    public void addFirst(int data) {
        ListNode listNode = new ListNode(data);
        if (head == null){//注意为空的情况
            head = listNode;
            last = listNode;
        }else{//注意加上else,否则在一开始的时候,listnode.next为head,next就会被置为head
            //就会永远在头结点处死循环
            listNode.next = head;
            head.pre = listNode;
            head = listNode;
        }
    }

    /**
     * 尾插法
     * @param data
     */
    @Override
    public void addLast(int data) {
        ListNode listNode = new ListNode(data);
        if (head == null){
            head = listNode;
            last = listNode;
        }else {
            listNode.pre = last;
            last.next = listNode;
            last = last.next;
        }
    }

    private boolean checkIndex(int index){//检查index是否合法
        if (index > size() ||index < 0){
            return false;
        }
        return true;
    }
    private ListNode findNode(int index) {//找到对应下标的结点
        ListNode cur = head;
        int count = 0;
        while (count != index){
            count ++;
            cur = cur.next;
        }
        return cur;
    }

    /**
     * 在指定位置插入结点
     * @param index
     * @param data
     */
    @Override
    public void addIndex(int index, int data) {
        if (!checkIndex(index)){
            throw new IndexExecption("下标输入有误");
        }
        if (index == 0){
            addFirst(data);
            return;//记得返回,不然下面的代码也会执行
        }
        if (index == size()){
            addLast(data);
            return;
        }
        ListNode listNode = new ListNode(data);
        ListNode cur = findNode(index);
        listNode.next = cur;
        listNode.pre = cur.pre;
        cur.pre.next = listNode;
        cur.pre = listNode;

    }

    /**
     * 查看链表中是否包含指定元素
     * @param key
     * @return
     */
    @Override
    public boolean contains(int key) {
        if (head == null){
            return false;
        }
        ListNode cur = head;
        while (cur != null){//先遍历链表
            if (cur.val == key){
                return true;//找到相等的值直接返回true
            }
            cur = cur.next;
        }
        return false;//跳出来就证明已经走到了终点,没找到
    }

    /**
     * 删除第一个值为key的结点
     * @param key
     */
    @Override
    public void remove(int key) {
        ListNode cur = head;
        while(cur != null){//cur向下遍历
            if (cur.val == key){//cur找到的清空
                if (cur == head){//如果cur为头结点
                    head = head.next;//head向后移动
                    if (head != null){
                        head.pre = null;
                    }else {//如果cur为头结点且只有一个结点
                        last = null;//last也置为空
                    }
                }else {//cur不为头结点
                    if (cur.next != null){//cur为中间结点
                        cur.pre.next = cur.next;
                        cur.next.pre = cur.pre;
                    }else {//cur为尾结点
                        cur.pre.next = null;
                        last = last.pre;
                    }
                }
                return;//删完返回
            }
            cur = cur.next;//cur向下走
        }
    }

    /**
     * 删除所有值为key结点
     * @param key
     */
    @Override
    public void removeAllKey(int key) {
        ListNode cur = head;
        while(cur != null){//cur向下遍历
            if (cur.val == key){//cur找到的清空
                if (cur == head){//如果cur为头结点
                    head = head.next;//head向后移动
                    if (head != null){
                        head.pre = null;
                    }else {//如果cur为头结点且只有一个结点
                        last = null;//last也置为空
                    }
                }else {//cur不为头结点
                    if (cur.next != null){//cur为中间结点
                        cur.pre.next = cur.next;
                        cur.next.pre = cur.pre;
                    }else {//cur为尾结点
                        cur.pre.next = null;
                        last = last.pre;
                    }
                }//直接把return去掉,删完不返回,继续删
            }
            cur = cur.next;//cur向下走
        }
    }

    /**
     * 计算链表大小
     * @return
     */
    @Override
    public int size() {
        int count = 0;
        ListNode cur = head;
        while (cur != null){
            cur = cur.next;
            count++;
        }
        return count;
    }

    /**
     * 打印链表
     */
    @Override
    public void display() {
        ListNode cur = head;
        while (cur != null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println();
    }

    /**
     * 清空链表
     */
    @Override
    public void clear() {
        ListNode cur = head;
        while (cur != null){
            ListNode curNext = cur.next;//记录下一个结点
            cur.next = null;
            cur.pre = null;//每一个结点的next和pre都置空
            cur = curNext;
        }
        head = null;
        last = null;//head和last指向的仍然是原来的地址,cur只是修改了节点内的值,
        //所以head和last需要手动置空
    }
}

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

[注意事项]

在头插法和尾插法的过程中,如果该链表为空,在把该链表的头结点和尾结点都指向添加结点之后,记得后面不符合条件的语句用else括起来,否者在头插或尾插之后,还会执行head!=null的代码
在中间插入节点的时候,如果插入的结点为头插或者是尾插的时候,记得返回,否者和上面的一条一样,执行完头插和尾插之后,又会执行中间插入的代码.
删除代码的逻辑较为复杂,我们通过一张图来表示

测试上面实现的方法:

/**
 * 开始测试
 */
public class Test {
    public static void main(String[] args) {
        MyLinkedList_2 myLinkedList_2 = new MyLinkedList_2();
        myLinkedList_2.addFirst(1);
        myLinkedList_2.addFirst(2);
        myLinkedList_2.addFirst(3);
        myLinkedList_2.addFirst(4);
        myLinkedList_2.display();
        MyLinkedList_2 myLinkedList_21 = new MyLinkedList_2();
        myLinkedList_21.addLast(1);
        myLinkedList_21.addLast(2);
        myLinkedList_21.addLast(3);
        myLinkedList_21.addLast(4);
        myLinkedList_21.display();
        myLinkedList_21.addIndex(1,34);
        myLinkedList_21.addIndex(2,45);
        myLinkedList_21.display();
        MyLinkedList_2 myLinkedList_22 = new MyLinkedList_2();
        myLinkedList_22.addIndex(0,1);
        myLinkedList_22.addIndex(1,2);
        myLinkedList_22.addIndex(2,3);
        myLinkedList_22.display();
        System.out.println(myLinkedList_22.contains(2));
        System.out.println(myLinkedList_22.contains(4));
        myLinkedList_21.remove(2);
        myLinkedList_21.display();
        MyLinkedList_2 myLinkedList_23 = new MyLinkedList_2();
        MyLinkedList_2 myLinkedList_24 = new MyLinkedList_2();
        myLinkedList_23.addFirst(1);
        myLinkedList_23.remove(1);
        myLinkedList_23.display();
        myLinkedList_24.remove(1);
        MyLinkedList_2 myLinkedList_25 = new MyLinkedList_2();
        myLinkedList_25.addFirst(2);
        myLinkedList_25.remove(1);
        MyLinkedList_2 myLinkedList_26 = new MyLinkedList_2();
        myLinkedList_26.addFirst(1);
        myLinkedList_26.addFirst(1);
        myLinkedList_26.addFirst(1);
        myLinkedList_26.addFirst(1);
        myLinkedList_26.addFirst(1);
        myLinkedList_26.addFirst(2);
        myLinkedList_26.removeAllKey(1);
        myLinkedList_26.display();
    }
}

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

测试结果:

在这里插入图片描述

2. LinkedList的使用

LinkedList的底层是双向无头非循环链表结构，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高.

2.1 构造方法

方法	说明
public LinkedList()	无参构造方法
public LinkedList(Collection<? extends E> c)	使用容器中的其他容器来构造,传入的容器中的数据类型必须是E的子类,以便兼容

public class LinkedList1 {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        List<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        list1.add(3);
        LinkedList<Number> list2 = new LinkedList<>(list1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2 常用方法

方法	说明
boolean add(E e)	尾插 e
void add(int index, E element)	将 e 插入到 index 位置
boolean addAll(Collection<? extends E> c)	尾插 c 中的元素
E remove(int index)	删除 index 位置元素
boolean remove(Object o)	删除遇到的第一个 o
E get(int index)	获取下标 index 位置元素
E set(int index, E element)	将下标 index 位置元素设置为 element
void clear()	清空
boolean contains(Object o)	判断 o 是否在线性表中
int indexOf(Object o)	返回第一个 o 所在下标
int lastIndexOf(Object o)	返回最后一个 o 的下标
List subList(int fromIndex, int toIndex)	截取部分 list

public static void main(String[] args) {
	LinkedList<Integer> list = new LinkedList<>();
	list.add(1); // add(elem): 表示尾插
	list.add(2);
	list.add(3);
	list.add(4);
	list.add(5);
	list.add(6);
	list.add(7);
	System.out.println(list.size());
	System.out.println(list);
	// 在起始位置插入0
	list.add(0, 0); // add(index, elem): 在index位置插入元素elem
	System.out.println(list);
	list.remove(); // remove(): 删除第一个元素，内部调用的是removeFirst()
	list.removeFirst(); // removeFirst(): 删除第一个元素
	list.removeLast(); // removeLast(): 删除最后元素
	list.remove(1); // remove(index): 删除index位置的元素
	System.out.println(list);
	// contains(elem): 检测elem元素是否存在，如果存在返回true，否则返回false
	if(!list.contains(1)){
		list.add(0, 1);
	}
	list.add(1);
	System.out.println(list);
	System.out.println(list.indexOf(1)); // indexOf(elem): 从前往后找到第一个elem的位置
	System.out.println(list.lastIndexOf(1)); // lastIndexOf(elem): 从后往前找第一个1的位置
	int elem = list.get(0); // get(index): 获取指定位置元素
	list.set(0, 100); // set(index, elem): 将index位置的元素设置为elem
	System.out.println(list);
	// subList(from, to): 用list中[from, to)之间的元素构造一个新的LinkedList返回
	List<Integer> copy = list.subList(0, 3); 
	System.out.println(list);
	System.out.println(copy);
	list.clear(); // 将list中元素清空
	System.out.println(list.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

2.3 LinkedList的遍历

import java.util.*;

public class LinkedList1 {
    public static void main(String[] args) {
        LinkedList<Integer> list = new LinkedList<>();
        list.add(1);
        list.add(2);
        list.add(3);
        System.out.println(list);//通过sout遍历
        for (int x: list) {//通过for_each遍历
            System.out.print(x+" ");
        }
        ListIterator<Integer> iterator = list.listIterator();
        while (iterator.hasNext()){//通过迭代器向后遍历
            System.out.println(iterator.next());
        }
        ListIterator<Integer> iterator1 = list.listIterator(list.size());
        while (iterator1.hasPrevious()){//通过迭代器向前遍历
            System.out.println(iterator1.previous());
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

面试题 ArrayList与LinkedList的区别
从插入,修改,删除,查找这几方面来说

插入:顺序表在插入的时候必须把插入点之后的元素全部后移,而链表不需要
修改:顺序表可以直接根据下标找到要修改的元素,而链表需要遍历
删除:顺序表删除点之后的元素必须向前移动,而链表不需要
查找: 顺序表可以直接根据下标查找,而链表需要遍历

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/AllinToyou/article/detail/504465