【数据结构】 LinkedList的模拟实现与使用-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】 LinkedList的模拟实现与使用。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

🍀什么是LinkedList

LinkedList 的官方文档
LinkedList的底层是双向链表结构(链表后面介绍)，由于链表没有将元素存储在连续的空间中，元素存储在单独的节点中，然后通过引用将节点连接起来了，因此在在任意位置插入或者删除元素时，不需要搬移元素，效率比较高。
【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现

🌴LinkedList的模拟实现

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

🚩创建双链表

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

双链表所需要元素

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

如下图所示：
【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现
代码实现如下：

    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;//尾节点

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

🚩头插法

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现

实现思路：

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

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现

代码实现如下：

    //插法 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;
        }
    }

🚩尾插法

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现
实现思路与头插法类似：

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

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现
代码实现如下：

    //尾插法 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;
    }

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现

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

我们先将node的next置为cur；
让cur前驱节点所指向的节点的后继节点指向node
再将cur的前驱节点给node的前驱节点
最后将cur的前驱节点置为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;

    }

🚩查找关键字

直接遍历查找即可

代码实现如下

    //查找是否包含关键字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;
 }

📌删除的是中间节点

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现

我们分为两步：

将cur的前驱节点的后继节点变为cur的后继节点
将cur的后继节点的前驱节点变为cur的前驱节点

代码实现如下：

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

📌删除节点为尾节点

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现

其实我们也分为两步：

将cur的前驱节点的后继节点变为cur的后继节点
将cur的前驱节点设为新的尾节点

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

代码实现如下：

 //中间  尾巴
 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接口，具体如下：
【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现

【说明】

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

🚩LinkedList的构造

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现
构造代码如下：

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的其他常用方法介绍

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现
方法使用代码如下：

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的区别

【数据结构】 LinkedList的模拟实现与使用,数据结构,数据结构,LinKedList,java,链表,双链表,模拟实现

⭕总结

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

到了这里，关于【数据结构】 LinkedList的模拟实现与使用的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！