Java数据结构——————双向链表（详细图解，增删改查详细实现）

目录1.什么是双向链表？2.双向链表的基本功能和结构3.双向链表基本功能详细图解代码实现1.清空，判空，获得长度功能实现2.获取第一个元素和最后一个元素3.添加元素t4.向指定位置i插入元素t5.获取指定位置i处的元素6.找到元素t第一次出现的位置7.删除位置i的元素，并返回该元素1.什么是双向链表？要明白什么是双向链表...

执梗

6312人浏览 · 2021-10-21 21:29:59

执梗 · 2021-10-21 21:29:59 发布

1.什么是双向链表？

要明白什么是双向链表，我们首先得明白什么是链表和什么是单链表？如果对于这个还有疑惑的推荐我的这篇博客，里面有非常详细的图解和代码实现。https://blog.csdn.net/m0_57487901/article/details/120871022?spm=1001.2014.3001.5501

首先我们通过一张直观的图对比单链表和双向链表

通过名字我们就可知它之所以叫双向链表，就是它可以向两头遍历，任意一个结点我可以得到它的前结点和后一个结点。不像单链表具有单向遍历的局限性，而且双向链表同时记录了尾结点last，这样我们每次想得到最后一个结点就不需要从头遍历到末尾了，如果链表很长的话，这样每次循环查询是非常浪费时间的。

2.双向链表的基本功能和结构

public class TwoWayLinkList<T> implements Iterable {
    //首结点
     Node head;
    //链表的长度
     int N;
     Node last;
    //结点类
    public class Node {
        //数据域
        public T item;
        //头指针
        public Node pre;
        //尾指针
        public Node next;

        public Node(T item, Node pre, Node next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }
    //初始化链表
    public TwoWayLinkList() {
        //初始化头结点和尾结点
        this.head = new Node(null, null, null);
        this.last = new Node(null, null, null);
        //初始化元素个数
        N = 0;
    }

解析：学习数据结构，我们在学习它的基本功能前，一定要明白它的逻辑结构。代码中，首先有一个内部类Node表示为结点，因为一个结点具有指针域和数据域，所以需要用一个类来表示，Node里面首先有表示存放数据的item，因为不清楚存放的数据是什么类型，所以用泛型T表示。同时有两个Node类型的变量pre和next分别记录指向前一个结点和后一个结点。在链表中有两个个Node类型的变量head和last分别表示头指针和尾指针，同时有一个int类型的N记录成员个数。初始化时，只需要建立头结点和尾结点，内部属性都为null，再让N为0即可。

public void clear()	清空链表
public int getLength()	获取链表长度
public boolean isEmpty()	判断链表是否为空
public T getFirst()	获取第一个元素
public T getLast()	获取最后一个元素
public void add(T t)	插入元素t
public void insert(int i,T t)	向指定位置i位置插入元素t
public T get(int i)	获取指定位置i处的元素
public int indexOf(T t) public T remove(int i)	找到元素t第一次出现的位置删除位置i处的元素,并返回该元素

看上去很多API功能需要实现，但其实大部分都很简单，只要理解就可以自己写出来。

3.双向链表基本功能详细图解代码实现

1.清空，判空，获得长度功能实现

//清空链表
    public void clear() {
        this.head.next = null;
        this.last = null;
        this.N = 0;
    }

    //获取链表长度
    public int getLength() {
        return N;
    }

        //判断链表是否为空
    public boolean isEmpty() {
        return N == 0;
    }

解析：这里我需要提醒大家，虽然头结点我们一般不存储元素，但是尾结点我们是可以存储的元素的，不要硬性思维。清空时，我们需要让头结点的next为null，这样无法从头进入链表，尾结点因为也是存储数据的，所以得直接让last为null，同时让N为0。获得链表长度直接返回N。判空也是直接返回N是否等于0的值即可。

2.获取第一个元素和最后一个元素

 //获取第一个元素
    public T getFirst() {
        //需要判断链表是否为空
        if (isEmpty()) {
            return null;
        }
        return head.next.item;
    }

    //获取最后一个元素
    public T getLast() {
        if (isEmpty()) {
            return null;
        }
        return last.item;
    }

解析：无论是获取哪个，我们都需要获取判空操作，养成好习惯，代码一定要考虑进所有情况，否则容易出异常。因为是获取元素，所以我们返回的一定是某个结点的item，第一个元素，说明就是头结点的next的item，最后一个元素就是返回last的item就好。

3.添加元素t

     //插入元素t
        public void add(T t) {
            //如果链表为空
            if (isEmpty()) {
                //创建新结点
                Node newNode = new Node(t, head, null);
                //让新节点为尾结点
                last = newNode;
                //让头结点指向尾结点
                head.next = last;
            } else {
                //如果链表不为空
                Node oldLast = last;
                //创建新节点
                Node newNode = new Node(t, oldLast, null);
                //让当前的尾结点指向新结点
                oldLast.next = newNode;
                //让新节点成为尾结点
                last = newNode;
            }
            N++;
        }

解析：同样我们需要对链表进行判空操作，如果链表为空，我们需要new一个新节点存入数据t，因为就它一个结点，所以我们把它赋值给last，让它成为尾结点，然后让head指向它即可。如果链表不为空，我们首先需要用一个结点oldLast记录旧的尾结点，同时new一个新节点放入数据t，让它成为新的尾结点last，同时让旧的尾结点oldLast指向它。最后无论怎样都记得让N++。

4.向指定位置i插入元素t

 //向指定位置i位置插入元素t
    public void insert(int i,T t){
        //找到i位置的前一个节点
        Node a=head;
        for (int j = 0; j < i; j++) {
            a=a.next;
        }
        //找到i位置的节点
        Node curr = a.next;
        //创建新节点
        Node newNode = new Node(t, a, curr);
        //让i位置的前一个节点的下一个节点变为新节点
        a.next=newNode;
        //让i位置的前一个节点变为新节点
        curr.pre=newNode;
        //元素个数加1
        N++;
    }

具体的步骤通过下图就能明白，一定要搞清楚每一步的顺序，否则很容易出错，自己可以草稿画图模拟。

5.获取指定位置i处的元素

 //获取指定位置i处的元素
    public T get(int i){
        Node a=head;
        for (int j = 0; j <=i; j++) {
            a=a.next;
        }
        return a.item;
    }

解析：和单链表相同，从头结点开始遍历打i处，返回item即可。

6.找到元素t第一次出现的位置

 //找到元素t第一次出现的位置
    public int indexOf(T t){
        Node a=head;
        for (int i = 0; i < N; i++) {
            a=a.next;
            if(a.item==t) return i;
        }
        return -1;
    }

解析：单单链表一致，从头结点开始遍历，同时判断是否是查找的元素，如果找到返回位置i，否则循环结束后返回-1。

7.删除位置i的元素，并返回该元素

//删除位置i处的元素,并返回该元素
    public T remove(int i){
        Node a=head;
        //找到i节点
        for (int j = 0; j <= i; j++) {
            a=a.next;
        }
        a.next.pre=a.pre;
        a.pre.next=a.next;
        N--;
        return a.item;
    }

如下图解即可明白，主要是要分清步骤，不要搞混，返回的是值不是结点。