数据结构之双向链表详解

😽博主CSDN主页：小源_😽

🖋️个人专栏：《数据结构》🖋️

😀努力追逐大佬们的步伐~

1. 前言

上一篇文章中我们重点讲解了无头单向非循环链表的模拟实现，现在我们来讲解LinkedList（无头双向链表实现）的模拟实现。

本章重点：

本文着重讲解了LinkedList(无头双向单链表)的实现和LinkedList的使用。

2. LinkedList（无头双向链表）的模拟实现

从上图可以看出，无头双向链表和无头单向非循环链表结构类似，只是**在每个节点中加入了前一个节点的地址(用prev存储)**，使得每个节点可以访问前一个节点。其中第一个节点的前驱prev为空。

2.1 定义IList接口

无头双向链表的模拟实现要定义的接口和上一篇文章中无头单向非循环链表的模拟实现一样，即：

public interface IList {
    //头插法
    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 clear();
    //打印
    void display();
}

2.2 重写IList中的方法

定义一个MyLinkedList类来实现IList接口，并且重写IList中的方法

（选中IList,快捷键为Ctrl+O）：

首先需要定义一个内部类作为节点的类，用static修饰，代表只能在当前类中使用。

接着定义一个头节点head，尾节点last。

public class MyLinkedList implements IList{
    static class ListNode {
        public int val;
        public ListNode next;
        public ListNode prev;

        public ListNode(int val) {
            this.val = val;
        }
    }

    public ListNode head;
    public ListNode last;

    @Override
    public void addFirst(int data) {

    }

    @Override
    public void addLast(int data) {

    }

    @Override
    public void addIndex(int index, int data) {

    }

    @Override
    public boolean contains(int key) {
        return false;
    }

    @Override
    public void remove(int key) {

    }

    @Override
    public void removeAllKey(int key) {

    }

    @Override
    public int size() {
        return 0;
    }

    @Override
    public void clear() {

    }

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

2.3 display（打印方法）

遍历双向链表的方法和遍历单链表相同：我们只需关心next域，而不需要关心prev。

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

2.4 size方法

求链表个数/长度

@Override
    public int size() {
        ListNode cur = head;
        //定义一个计数器
        int count = 0;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        return count;
    }

2.5 contains方法

指的是查找是否包含关键字key是否在单链表当中。这里跟size方法相似，只需遍历链表时判断是否cur.val == key

@Override
    public boolean contains(int key) {
        ListNode cur = head;
        while (cur != null) {
            //判断
            if (cur.val == key) {
                return true;
            }
            cur = cur.next;
        }
        return false;
    }

2.6 addFirst头插法

指的是将插入的节点存放在链表的第一个位置。

1.实例化一个节点

2.改变插入节点的next和prev

3.改变head

@Override
    public void addFirst(int data) {
        ListNode node = new ListNode(data);
        //如果head为空，则head和last都指向node
        if (head == null) {
            head = node;
            last = node;
        } else {
            node.next = head;
            head.prev = node;
            head = node;
        }
    }

2.7 addLast尾插法

指的是将插入的节点存放在链表的第一个位置。

1.实例化一个节点

2.找到最后一个节点last

3.last.next = node;

node.prev = last;

4.改变last

@Override
    public void addLast(int data) {
        ListNode node = new ListNode(data);
        //如果head为空，则head和last都指向node
        if (head == null) {
            head = node;
            last = node;
        } else {
            last.next = node;
            node.prev = last;
            last = node;
        }
    }

2.8 addIndex任意插法

指的是在任意位置插入一个节点。

1.让cur走index步(单链表的addIndex任意插法为走（index - 1）步)

2.node.next = cur.next;（还是先绑定后面的节点）

cur.prev.next = node;

node.prev = cur.prev;

cur.prev = node;

@Override
    public void addIndex(int index, int data) {
        int len = size();
        //检查index是否合法
        if(index < 0 || index > len) {
            //可以抛出自定义异常
            System.out.println("index位置不合法：" + index);
            return;
        }
        if (index == 0) {
            addFirst(data);
            return;
        }
        if (index == size()) {
            addLast(data);
            return;
        }
        //用cur接收前驱
        ListNode cur = findIndex(index);
        //实例化一个新的节点
        ListNode node = new ListNode(data);
        node.next = cur;
        cur.prev.next = node;
        node.prev = cur.prev;
        cur.prev = node;
    }

    //找到要插入的位置
    public ListNode findIndex(int index) {
        ListNode cur = head;
        while (index != 0) {
            cur = cur.next;
            index--;
        }
        return cur;
    }

2.9 remove方法

指的是删除第一次出现关键字为key的节点。

1.直接让cur走到index位置

2.删除

@Override
    public void remove(int key) {
        ListNode cur = head;

        while (cur != null) {
            if (cur.val == key) {
                //删除头节点
                if (cur == head) {
                    head = head.next;
                    head.prev = null;
                } else {
                    cur.prev.next = cur.next;
                    //删除最后一个节点
                    if (cur.next == null) {
                        last = last.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            } else {
                cur = cur.next;
            }
        }
    }

效果图如下：看似很正常，实际上还存在问题（当节点只有一个时的问题）

如图：第108行代码中，当节点只有一个的情况下，head.next为空,null.prev这一操作会报空指针异常

解决方法如下：

效果图如下：此时正常执行

remove方法的最终代码为：

@Override
    public void remove(int key) {
        ListNode cur = head;

        while (cur != null) {
            if (cur.val == key) {
                //删除头节点
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        //这是开始的代码，在head ！= null的前提下才能执行这行代码
                        head.prev = null;
                    }
                    last = null;
                } else {
                    cur.prev.next = cur.next;
                    //删除最后一个节点
                    if (cur.next == null) {
                        last = last.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
                return;
            } else {
                cur = cur.next;
            }
        }
    }

2.10 removeAllKey方法

指的是删除所有值为key的节点。

和remove方法类似，只需把删除操作的一段代码结束以后，不return ,继续cur = cur.next即可

@Override
    public void removeAllKey(int key) {
        ListNode cur = head;

        while (cur != null) {
            //删除
            if (cur.val == key) {
                //删除头节点
                if (cur == head) {
                    head = head.next;
                    if (head != null) {
                        //这是开始的代码，在head ！= null的前提下才能执行这行代码
                        head.prev = null;
                    }
                    last = null;
                } else {
                    cur.prev.next = cur.next;
                    //删除最后一个节点
                    if (cur.next == null) {
                        last = last.prev;
                    } else {
                        cur.next.prev = cur.prev;
                    }
                }
            }
            cur = cur.next;
        }
    }

2.11 clear方法

指的是删除链表的所有节点。

1.直接把头节点和尾巴节点置空的方法太粗糙，我们下面学习更细节的写法：

2.遍历链表，把每个节点的 val = null, prev = null, next = null 即可（val = null可以不写，因为没有人指向这个节点的时候，会被系统自动回收）

@Override
    public void clear() {
        ListNode cur = head;
        while (cur != null) {
            //用curNext记录cur.next，因为接下来cur.next将会改变为null
            //  我们要用curNext来继续遍历链表
            ListNode curNext = cur.next;
            cur.val = 0;
            cur.next = null;
            cur.prev = null;
            cur = curNext;
        }
        head = null;
        //暴力做法
//        head = null;
//        last = null;
    }

3. LinkedList的使用

3.1 什么是LinkedLList

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

在集合框架中，LinkedList也实现了List接口

【说明】

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

3.2 LinkedList的使用

1.LinkedList的构造
方法解释
LinkedList()

无参构造

public LinkedList(Collection<? extends E> c)
使用其他集合容器中元素构造List

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);
}

2.2. LinkedList的其他常用方法介绍

  方法

解释

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)
返回最后i一个 o 所在下标
List<E> subList(int fromIndex, int toIndex)
截取部分 list
```
import java.util.LinkedList;
import java.util.List;

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


 效果图如下：

![](https://img-blog.csdnimg.cn/direct/decdef49288f449992f21d34b27a0b45.png)

### 3.3 LinkedList的遍历

import java.util.LinkedList;
import java.util.ListIterator;

public class TestLink {
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("======");

    // 1.直接打印，因为LinkedList底层实现了List的toString方法
    System.out.println(list);
    System.out.println("======");

    // 2.foreach遍历
    for (int e:list) {
        System.out.print(e + " ");
    }
    System.out.println();
    System.out.println("======");

    // 3.for循环
    for (int i = 0; i < list.size(); i++) {
        System.out.print(list.get(i) + " ");
    }
    System.out.println();
    System.out.println("======");

    // 4.使用迭代器遍历---正向遍历
    ListIterator<Integer> it = list.listIterator();
    while(it.hasNext()){
        System.out.print(it.next()+ " ");
    }
    System.out.println();
    System.out.println("===反向===");

    // 5.使用反向迭代器---反向遍历
    ListIterator<Integer> rit = list.listIterator(list.size());
    while (rit.hasPrevious()){
        System.out.print(rit.previous() +" ");
    }
    System.out.println();
}

}

```

效果图如下：

4. 经常遇到的面试问题

1.ArrayList和LinkedList的区别是什么？/2.顺序表和链表的区别是什么？/3.数组（和顺序表类似）和链表的区别？

（这三个问题其实是一个问题）

答：

如果是经常根据下标进行查找的使用顺序表（ArrayList）

如果经常进行插入和删除操作的可以使用链表（LinkedList）

下图是ArrayList和LinkedList的其他区别：

最后，祝大家天天开心，更上一层楼！关注我🌹，我会持续更新学习分享...🖋️

标签：链表数据结构学习

本文转载自: https://blog.csdn.net/2302_81666448/article/details/135093661
版权归原作者 小源_ 所有，如有侵权，请联系我们删除。