【数据结构】从链表到LinkedList类

🧧🧧🧧🧧🧧个人主页🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧数据结构专栏🎈🎈🎈🎈🎈
🧧🧧🧧🧧🧧上一篇文章：从顺序表到ArrayList类🎈🎈🎈🎈🎈

1.前言

上一篇文章我们了解ArrayList表的使用，并且模拟了ArrayList表，通过数组的方式来存储数据单元。其底层是一块连续储存的空间，这时候我们发现当我们去插入数据或者删除数据的时候，需要将前后的数据整体向前移动或者向后移动。因此ArrayList是不能满足我们的需求。接下来我们可以来看看即将要学的LinkedList表。

2.链表

2.1 链表的概念及结构

链表是一种物理存储结构上非连续存储结构，数据元素的逻辑顺序是通过链表中的引用链接次序实现的 。结构像我们平时坐的交通工具火车一样，一节一节的，并不是按一定的顺序链接的，车厢可以随意链接，链表也是这样的。


注意：
1.从图中可以看出，链式结构不一定在物理上是连续的空间，但在逻辑上是连续的空间。
2.现实中的结点一般都是在堆上申请出来的。
3。在堆上申请的空间，是按定一定的规则来分配的，两次申请的空间可能是连续的空间，也有可能不是连续的空间。

2.2链表的组合

在现实当中有很多种的链表，有分单向和双向，带头和不带头，循环和不循环，总共有八种组合方式：
1.单向带头循环

2.单向带头不循环

3.单向不带头循环

4.单向不带头不循环

5.双向带头循环

6.双向带头不循环

7.双向不带头循环

8.双向不带头不循环

这么多种类型的链表，我们只了解两种单向不带头不循环和双向不带头不循环。
单向不带头不循环：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
双向不带头不循环：在Java的集合框架库中LinkedList底层实现就是无头双向循环链表。

2.3链表的实现

2.3.1头插法

public void addFirst(int data) {
        ListNode node = new ListNode(data);
        //如果没有节点,直接将head标记放在要插的节点上，作为第一个首节点
        if(head == null) {
            this.head = node;
        }
        else {
            //先绑定，再移标记引用变量
            node.next = this.head;
            this.head = node;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12

2.3.2尾插法

public void addLast(int data) {
        ListNode node = new ListNode(data);
        //如果没有节点,直接将head标记放在要插的节点上，作为第一个尾节点
        if(head == null) {
            this.head = node;
        }
        else {
            ListNode cur = head;
            while(cur.next != null) {
                cur = cur.next;
            }
            cur.next = node;
        }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.3.3任意位置插入,第一个数据节点为0号下标

public void addIndex(int index, int data) {
        //判断index是否合法
        if(index < 0 || index > size()) {
            throw new IndexException("坐标"+index+":位置不合法");
        }
        ListNode node = new ListNode(data);
        //1.如果从头插入，直接头插法
        if(index == 0) {
            addFirst(data);
        }
        //2.从中间插
            ListNode cur = searchPrevIndex(index);
            node.next = cur.next;
            cur.next = node;
    }
    //创建一个找前驱的方法
    private ListNode searchPrevIndex(int index) {
        ListNode cur = head;
        int count = 0;
        while(count < index-1) {
            cur = cur.next;
            count++;
        }
        return cur;
    }
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

2.3.4查找是否包含关键字key是否在单链表当中

public boolean contains(int key) {
        ListNode cur = head;
        while(cur != null) {
            if(key == cur.value) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }
1
2
3
4
5
6
7
8
9
10

2.3.5删除第一次出现关键字为key的节点

public void remove(int key) {
        //删除头节点
        if(head.value == key) {
            head = head.next;
            return;
        }
        //1.找到要删除key的前驱
        ListNode cur = searchPrevKey(key);
        if(cur == null) {
            return;//没有你要删除的key
        }
        //2.定义一个标记curNext
        ListNode curNext = cur.next;
        //3.删除key
        cur.next = curNext.next;
    }
    private ListNode searchPrevKey(int key) {
        ListNode cur = head;
        while(cur.next != null) {
            if(cur.next.value == key) {
                return cur;
            }
            else {
                cur = cur.next;
            }
        }
        return null;
    }
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

2.3.6删除所有值为key的节点(非循环方法)

public void removeAllKeye(int key) {
        ListNode prev = head;
        ListNode cur = head.next;
        while (cur != null) {
            if(cur.value == key) {
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        //删除头节点
        if(head.value == key) {
            head = head.next;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

2.3.7得到单链表的长度

public int size() {
        ListNode cur =head;
        int count = 0;
        while(cur != null) {
            cur = cur.next;
            count++;
        }
        return count;
    }
1
2
3
4
5
6
7
8
9

2.3.8清空链表

 public void clear() {
    head = null;
    }
}

1
2
3
4
5

2.4LinkedList的模拟实现

** 2.4。1头插法**

public void addFirst(int data) {
        ListNode node = new ListNode(data);
        //如果链表为空
        if(head == null) {
            head = node;
            last = node;
        }
        else {
            //链表不为空
            node.next = head;
            head.prev = node;
            node.prev = null;
            head = node;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

** 2.4。2尾插法**

public void addLast(int data) {
        ListNode node = new ListNode(data);
        //如果链表为空
        if(head == null) {
            head = node;
            last = node;
        }
        else {
            //链表不为空
            last.next = node;
            node.prev = last;
            node.next = null;
            last = node;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

** 2.4.3任意位置插入,第一个数据节点为0号下标**

public void addIndex(int index, int data) {
        //先判断index合不合法
        if(index<0 || index >size()) {
            throw new IndexException("位置不合法:"+index);
        }
        //1.从头插入，头插法
        if(index == 0) {
            addFirst(data);
            return;
        }
        //2.从尾插，尾插法
        if(index == size()) {
            addLast(data);
            return;
        }
        //3.从中间插
        //找要插入的位置
        ListNode cur = findAddIndex(index);
        ListNode node = new ListNode(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }
    private ListNode findAddIndex(int index) {
        ListNode cur = head;
        while(index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }
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

** 2.4.4查找是否包含关键字key是否在单链表当中**

public boolean contains(int key) {
       ListNode cur = head;
       while(cur != null) {
           if(cur.value == key) {
               return true;
           }
           else {
               cur = cur.next;
           }
       }
       return false;
    }
1
2
3
4
5
6
7
8
9
10
11
12

** 2.4.5删除第一次出现关键字为key的节点**

 public void remove(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.value == key) {
                if(cur == head) {
                    //删除头节点
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }else {
                        //只有一个节点 且是需要删除的节点
                        last = null;
                    }
                }else {
                    //删除中间节点
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                        cur.prev.next = cur.next;
                    }else {
                        //删除尾巴节点
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }
                }
                return;
            }
            cur = cur.next;
        }
    }
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

** 2.4.6删除所有值为key的节点**

 public void removeAllKeye(int key) {
        ListNode cur = head;
        while (cur != null) {
            if(cur.value == key) {
                if(cur == head) {
                    head = head.next;
                    if(head != null) {
                        head.prev = null;
                    }else {
                        //只有一个节点 且是需要删除的节点
                        last = null;
                    }
                }else {
                    //删除中间节点
                    if(cur.next != null) {
                        cur.next.prev = cur.prev;
                        cur.prev.next = cur.next;
                    }else {
                        //删除尾巴节点
                        cur.prev.next = cur.next;
                        last = last.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }
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

** 2.4.7得到双链表的长度**

public int size() {
        ListNode cur = head;
        int count = 0;
        while(cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }
1
2
3
4
5
6
7
8
9

** 2.4.8清除链表**

public void clear() {
    head =null;
    last =null;
    }
1
2
3
4

3.ArrayList和LinkedList的区别

结尾：
希望大家可以给我点点关注，点点赞，你们的支持就是我的最大鼓励。🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹🌹