【数据结构】 LinkedList的模拟实现与使用

Love The Way You Lie 2024-04-17 10:43 79阅读 0赞

#### 文章目录 ####

*  ?什么是LinkedList
 *  ?LinkedList的模拟实现
 *   *  ?创建双链表
     *  ?头插法
     *  ?尾插法
     *  ?任意位置插入
     *  ?查找关键字
     *  ?链表长度
     *  ?打印链表
     *  ?删除第一次出现关键字为key的节点
     *   *  ?删除的是头节点
         *  ?删除的是中间节点
         *  ?删除节点为尾节点
     *  ?删除所有值为key的节点
     *  ?清空链表
     *  ?完整代码实现
 *  ?LinkedList的使用
 *   *  ?LinkedList的构造
     *  ?LinkedList的其他常用方法介绍
     *  ?LinkedList的遍历
 *  ?ArrayList和LinkedList的区别
 *  ⭕总结

## ?什么是LinkedList ##

[LinkedList 的官方文档][LinkedList]  
LinkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。  
![在这里插入图片描述][f90f3ad58a684a3a807cbc8a339db64b.png]

## ?LinkedList的模拟实现 ##

我们在这里创建一个MyLinkedList的java文件用于模拟实现我们的LinkedList。

### ?创建双链表 ###

我们要模拟实现LinkendList，首先我们要有我们的双链表，这里我们来实现一个双链表

双链表所需要元素

*  前驱节点：用于存储前一节点的位置，用prev表示
 *  后继节点：用于储存下一节点的位置，用next表示
 *  所需要储存的数据，用val表示
 *  头节点：用head表示
 *  尾节点：用last表示

如下图所示：  
![在这里插入图片描述][db1a37b8fc15408498dadaf0cd5e47e5.png]  
代码实现如下：

static class ListNode {
        
            public int val;
            public ListNode prev;//前驱
            public ListNode next;//后继
    
            public ListNode(int val) {
        
                this.val = val;
            }
        }
    
        public ListNode head;//头节点
        public ListNode last;//尾节点

接下来我们将实现它的一些的功能

### ?头插法 ###

![在这里插入图片描述][c509ffa35cb8407bbaf27dd777cbf2bf.png]

实现思路：

*  首先判断头节点是否为null
 *  若为null，则该节点就是头节点，也是尾节点
 *  则将原先head的前驱节点指向位置改为新增节点位置
 *  新增节点后驱节点指向位置改为head节点的位置
 *  将新增节点设为新的头节点

![在这里插入图片描述][7ca8a32c3147430a9268d752f0d8e376.png]

代码实现如下：

//插法 O(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;
                head = node;
            }
        }

### ?尾插法 ###

![在这里插入图片描述][3546fe3137c145c0b1dcadc482790d15.png]  
实现思路与头插法类似：

*  首先判断头节点是否为null
 *  若为null，则该节点就是尾节点，也是头节点
 *  将last的后继节点设为node
 *  node的前驱节点设为last
 *  node设为新的尾节点

![在这里插入图片描述][494e8da7f820451089bc2db5271dcf95.png]  
代码实现如下：

//尾插法 O(1)
        public void addLast(int data){
        
            ListNode node = new ListNode(data);
            if(head == null) {
        
                head = node;
                last = node;
            }else {
        
                last.next = node;
                node.prev = last;
                last = node;
            }
        }

### ?任意位置插入 ###

首先我们需要对插入数据进行判断其合法线性

这里我们自定义一个异常，为ListIndexOutOfException

public class ListIndexOutOfException extends RuntimeException{
        
        public ListIndexOutOfException() {
        
        }
    
        public ListIndexOutOfException(String message) {
        
            super(message);
        }
    }

其次我们可以对插入数据进行判断，若是在头尾进行插入，则可以直接用头插法与尾插法进行搞定

当所插入数据在中间时，我们首先要找到需要插入的节点，并返回，用cur接收

private ListNode findIndex(int index) {
        
            ListNode cur = head;
            while (index != 0) {
        
                cur = cur.next;
                index--;
            }
            return cur;
        }

![在这里插入图片描述][e7be0e888af146a986aa9028ca7d7d5c.png]

当我们找到要插入的节点后，我们的步骤为以下几步

*  我们先将node的next置为cur；
 *  让cur前驱节点所指向的节点的后继节点指向node
 *  再将cur的前驱节点给node的前驱节点
 *  最后将cur的前驱节点置为node；
 *  ![在这里插入图片描述][d22937e8ca304a83a60e49bf0bc9ec25.png]

代码实现如下：

//任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
        
            if(index < 0 || index > size()) {
        
                throw new ListIndexOutOfException("违规数据");
            }
            if(index == 0) {
        
                addFirst(data);
                return;
            }
            if(index == size()) {
        
                addLast(data);
                return;
            }
    
            ListNode cur = findIndex(index);
            //
            ListNode node = new ListNode(data);
            node.next = cur;
            cur.prev.next = node;
            node.prev = cur.prev;
            cur.prev = node;
    
        }

### ?查找关键字 ###

直接遍历查找即可

代码实现如下

//查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
        
            ListNode cur = head;
            while (cur != null) {
        
                if(cur.val == key) {
        
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }

### ?链表长度 ###

用一个len变量进行记录，遍历链表，最后进行返回即可

代码实现如下：

public int size(){
        
            int len = 0;
            ListNode cur = head;
            while (cur != null) {
        
                len++;
                cur = cur.next;
            }
            return len;
        }

### ?打印链表 ###

遍历链表进行输出即可

代码实现如下：

public void display(){
        
            ListNode cur = head;
            while (cur != null) {
        
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }

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

我们大致的做法就是对链表进行遍历，遍历到相应的元素，删除即可，然后返回即可；

细分可分为三种情况

*  删除的是头节点
 *  删除的是中间节点
 *  删除的是尾节点

#### ?删除的是头节点 ####

我们只需要将head向前走一步就好

这时候又分为只一个节点和有多个节点的情况

当只有一个节点时，我们的head只需要向前走一步就好

如果有多个节点，我们还需要将新节点的前驱节点置为null；

代码实现如下：

head = head.next;
     //只有一个节点
     if(head != null) {
        
     	head.prev = null;
     }

#### ?删除的是中间节点 ####

![在这里插入图片描述][03d084df9ebb4fd0b9f1c7e82e1e9150.png]

我们分为两步：

*  将cur的前驱节点的后继节点变为cur的后继节点
 *  将cur的后继节点的前驱节点变为cur的前驱节点
 *  ![在这里插入图片描述][3faa461392474e3cb1062fbeae47639d.png]

代码实现如下：

cur.prev.next = cur.next;                   
    cur.next.prev = cur.prev;

#### ?删除节点为尾节点 ####

![在这里插入图片描述][a7c0969c399240be97db39872d839ad3.png]

其实我们也分为两步：

*  将cur的前驱节点的后继节点变为cur的后继节点
 *  将cur的前驱节点设为新的尾节点
 *  ![在这里插入图片描述][e2f362ec5a62433eb48a0bfafa200ca9.png]

我们发现其实前面一步和删除中间节点一样，所以这里我们将他们组合起来，在删除中间节点里面加入判断即可

代码实现如下：

//中间  尾巴
     cur.prev.next = cur.next;
    //不是尾巴节点
    if(cur.next != null) {
        
    	cur.next.prev = cur.prev;
    }else {
        
    //是尾巴节点
    	last = last.prev;
    }

删除完后直接返回就好，如此一来，我们删除第一次出现关键字为key的节点完整代码也就可以出来了

代码如下：

//删除第一次出现关键字为key的节点
        public void remove(int key){
        
            ListNode cur = head;
            while (cur != null) {
        
                //开始删除了
                if(cur.val == key) {
        
                    //1. 删除的是头节点
                    if(cur == head) {
        
                        head = head.next;
                        //只有一个节点
                        if(head != null) {
        
                            head.prev = null;
                        }
                    }else {
        
                        //中间  尾巴
                        cur.prev.next = cur.next;
                        //不是尾巴节点
                        if(cur.next != null) {
        
                            cur.next.prev = cur.prev;
                        }else {
        
                            //是尾巴节点
                            last = last.prev;
                        }
                    }
                    return;
                }
                cur = cur.next;
            }
        }

### ?删除所有值为key的节点 ###

这个代码实现起来与删除第一次出现关键字为key的节点几乎是一模一样的；

我们只需要return删掉就好

代码实现如下：

//删除所有值为key的节点
        public void removeAllKey(int key){
        
            ListNode cur = head;
            while (cur != null) {
        
                //开始删除了
                if(cur.val == key) {
        
                    //1. 删除的是头节点
                    if(cur == head) {
        
                        head = head.next;
                        //只有一个节点
                        if(head != null) {
        
                            head.prev = null;
                        }
                    }else {
        
                        //中间  尾巴
                        cur.prev.next = cur.next;
                        //不是尾巴节点
                        if(cur.next != null) {
        
                            cur.next.prev = cur.prev;
                        }else {
        
                            //是尾巴节点
                            last = last.prev;
                        }
                    }
                }
                cur = cur.next;
            }
        }

### ?清空链表 ###

我们只需要遍历整个链表，将每个节点的前驱与后继节点都置为null就好

代码实现如下：

public void clear(){
        
            ListNode cur = head;
            while(cur != null) {
        
                cur.prev  = null;
                cur = cur.next;
                cur.prev.next = null;
            }
            head = null;
            last = null;
        }

### ?完整代码实现 ###

public class MyLinkedList {
        
        static class ListNode {
        
            public int val;
            public ListNode prev;//前驱
            public ListNode next;//后继
    
            public ListNode(int val) {
        
                this.val = val;
            }
        }
    
        public ListNode head;//头节点
        public ListNode last;//尾节点
    
        //头插法 O(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;
                head = node;
            }
        }
        //尾插法 O(1)
        public void addLast(int data){
        
            ListNode node = new ListNode(data);
            if(head == null) {
        
                head = node;
                last = node;
            }else {
        
                last.next = node;
                node.prev = last;
                last = node;
            }
        }
        //任意位置插入,第一个数据节点为0号下标
        public void addIndex(int index,int data){
        
            if(index < 0 || index > size()) {
        
                throw new ListIndexOutOfException("违规数据");
            }
            if(index == 0) {
        
                addFirst(data);
                return;
            }
            if(index == size()) {
        
                addLast(data);
                return;
            }
    
            ListNode cur = findIndex(index);
            //
            ListNode node = new ListNode(data);
            node.next = cur;
            cur.prev.next = node;
            node.prev = cur.prev;
            cur.prev = node;
    
        }
        private ListNode findIndex(int index) {
        
            ListNode cur = head;
            while (index != 0) {
        
                cur = cur.next;
                index--;
            }
            return cur;
        }
        //查找是否包含关键字key是否在单链表当中
        public boolean contains(int key){
        
            ListNode cur = head;
            while (cur != null) {
        
                if(cur.val == key) {
        
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
        //删除第一次出现关键字为key的节点
        public void remove(int key){
        
            ListNode cur = head;
            while (cur != null) {
        
                //开始删除了
                if(cur.val == key) {
        
                    //1. 删除的是头节点
                    if(cur == head) {
        
                        head = head.next;
                        //只有一个节点
                        if(head != null) {
        
                            head.prev = null;
                        }
                    }else {
        
                        //中间  尾巴
                        cur.prev.next = cur.next;
                        //不是尾巴节点
                        if(cur.next != null) {
        
                            cur.next.prev = cur.prev;
                        }else {
        
                            //是尾巴节点
                            last = last.prev;
                        }
                    }
                    return;
                }
                cur = cur.next;
            }
        }
        //删除所有值为key的节点
        public void removeAllKey(int key){
        
            ListNode cur = head;
            while (cur != null) {
        
                //开始删除了
                if(cur.val == key) {
        
                    //1. 删除的是头节点
                    if(cur == head) {
        
                        head = head.next;
                        //只有一个节点
                        if(head != null) {
        
                            head.prev = null;
                        }
                    }else {
        
                        //中间  尾巴
                        cur.prev.next = cur.next;
                        //不是尾巴节点
                        if(cur.next != null) {
        
                            cur.next.prev = cur.prev;
                        }else {
        
                            //是尾巴节点
                            last = last.prev;
                        }
                    }
                }
                cur = cur.next;
            }
        }
    
        public int size(){
        
            int len = 0;
            ListNode cur = head;
            while (cur != null) {
        
                len++;
                cur = cur.next;
            }
            return len;
        }
    
        public void display(){
        
            ListNode cur = head;
            while (cur != null) {
        
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        public void clear(){
        
            ListNode cur = head;
            while(cur != null) {
        
                cur.prev  = null;
                cur = cur.next;
                cur.prev.next = null;
            }
            head = null;
            last = null;
        }
    }

## ?LinkedList的使用 ##

在集合框架中，LinkedList也实现了List接口，具体如下：  
![在这里插入图片描述][dd9390794abb43bfb9f1be6f3d6a9f7b.png]

【说明】

1.  LinkedList实现了List接口
2.  LinkedList的底层使用了双向链表
3.  LinkedList没有实现RandomAccess接口，因此LinkedList不支持随机访问
4.  LinkedList的任意位置插入和删除元素时效率比较高，时间复杂度为O(1)
5.  LinkedList比较适合任意位置插入的场景

### ?LinkedList的构造 ###

![在这里插入图片描述][fbbe7886f6634c4d973d29a9ec71e2a1.png]  
构造代码如下：

import java.util.LinkedList;
    import java.util.List;
    
    public class Main {
        
        public static void main(String[] args) {
        
    // 构造一个空的LinkedList
            List<Integer> list1 = new LinkedList<>();
            List<String> list2 = new java.util.ArrayList<>();
            list2.add("JavaSE");
            list2.add("JavaWeb");
            list2.add("JavaEE");
    // 使用ArrayList构造LinkedList
            List<String> list3 = new LinkedList<>(list2);
        }
    }

### ?LinkedList的其他常用方法介绍 ###

![在这里插入图片描述][d7958e0392414a1692de064d4eb01067.png]  
方法使用代码如下：

import java.util.LinkedList;
    import java.util.List;
    
    public class Main {
        
        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());
        }
    }

### ?LinkedList的遍历 ###

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());
    // foreach遍历
            for (int e:list) {
        
                System.out.print(e + " ");
            }
            System.out.println();
    // 使用迭代器遍历---正向遍历
            ListIterator<Integer> it = list.listIterator();
            while(it.hasNext()){
        
                System.out.print(it.next()+ " ");
            }
            System.out.println();
    // 使用反向迭代器---反向遍历
            ListIterator<Integer> rit = list.listIterator(list.size());
            while (rit.hasPrevious()){
        
                System.out.print(rit.previous() +" ");
            }
            System.out.println();
        }

## ?ArrayList和LinkedList的区别 ##

![在这里插入图片描述][59b0ffdccf61420cbed61f78772b9452.png]

## ⭕总结 ##

关于《【数据结构】 LinkedList的模拟实现与使用》就讲解到这儿，感谢大家的支持，欢迎各位留言交流以及批评指正，如果文章对您有帮助或者觉得作者写的还不错可以点一下关注，点赞，收藏支持一下！

[LinkedList]: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html
[f90f3ad58a684a3a807cbc8a339db64b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/97f4964e53424632937293d11297fae5.png
[db1a37b8fc15408498dadaf0cd5e47e5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/12209f1278634ab5ab43bdf9f261402f.png
[c509ffa35cb8407bbaf27dd777cbf2bf.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/4c14d989cb2f4ae9a54d3f9b30aadf82.png
[7ca8a32c3147430a9268d752f0d8e376.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/bf5887519dde434c819431952ee1a258.png
[3546fe3137c145c0b1dcadc482790d15.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/f9d04befa2e544a0a19affb4dd7e05f1.png
[494e8da7f820451089bc2db5271dcf95.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/358aaf91f9c947a7a59cbf94c3ec0808.png
[e7be0e888af146a986aa9028ca7d7d5c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/42a799edc0e6419cb4620000df6d7052.png
[d22937e8ca304a83a60e49bf0bc9ec25.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/35d291ade8164b808a22025555b2eb35.png
[03d084df9ebb4fd0b9f1c7e82e1e9150.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/20485e9dfc1d4899b0a4734a69a81b10.png
[3faa461392474e3cb1062fbeae47639d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/9297a6dc2a8f407281caf5c0715dbfd8.png
[a7c0969c399240be97db39872d839ad3.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/216ac7c6ea5140a7a423822a2d2b63f5.png
[e2f362ec5a62433eb48a0bfafa200ca9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/01abe993d9a34f528f0ad663462f363c.png
[dd9390794abb43bfb9f1be6f3d6a9f7b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/20f951a7bef141699e5ec1201dee3517.png
[fbbe7886f6634c4d973d29a9ec71e2a1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/d0eb14f053764b84a883bd03c1c2e0c6.png
[d7958e0392414a1692de064d4eb01067.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/fb2b7b2d76f24cb885f7a7e52e9cae00.png
[59b0ffdccf61420cbed61f78772b9452.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/4dc1ebc0dcb941c3a2ff95439e84c4ef.png