【数据结构】双向链表你必须知道的内部原理！！！

用户11288949

发布于 2024-09-24 13:41:45

830

发布于 2024-09-24 13:41:45

文章被收录于专栏：学习

📚️1.双向链表与单链表

🎥1.1特点：

1. 指针数量：单链表每个节点只有一个指向下一节点的指针；双向链表每个节点有两个指针，分别指向前一个节点和后一个节点。 2. 遍历方向：单链表只能从表头向表尾单向遍历；双向链表可以从表头向表尾和从表尾向表头双向遍历。

🎥1.2优缺点：

单链表：

结构相对简单，实现和操作较为容易，节省存储空间，因为每个节点只需要一个指针。但是无法快速找到前一个节点，反向遍历困难。 双向链表：

1. 可以方便地在前后两个方向上进行遍历，操作更加灵活。 2. 对于某些需要频繁查找前一个节点的操作，双向链表效率更高。

🌟🌟总结来说：双向链表可以反复横跳，所以要求空间高，而单链表只能从始至终，所以安分，空间要求不高。~~~哈哈哈，是不是浅显易懂。

📚️2.双向链表的模拟实现

😏接下来就是最重要的部分了~~~ 🎥2.1链表的构造

代码如下：

public class doubleLink {
    static class linknode {
        private int val;
        private linknode prve;
        private linknode next;

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

    private linknode head;
    private linknode last;

🌟和上期单链表一致，只不过多加了一个前驱指针，和一个尾巴节点。

🎥2.2头插法

代码如下：

//头插法
   public void addFirst(int data) {
        linknode node = new linknode(data);
        if (head == null) {        //判断头节点是否为空
            head = node;
            last = node;
        } else {                   //正常头插法
            node.next = head;
            head.prve = node;
            head = node;
        }
    }

//尾插法
    public void addLast(int data) {
        linknode node = new linknode(data);
        if (last == null) {           //判断尾巴节点是否为空，就是没有链表
            last = node;
            head = node;
        } else { 
            last.next = node;
            node.prve = last;
            last = node;
        }
    }

🌟在一般情况下，在头插时，头结点需要和插入的节点的，前驱后记相连，最后将头结点表示给插入的节点，尾插法也基本一致。但是注意的是：都要考虑链表为空的情况。

🎥2.3任意位置插入

代码如下：

public void addIndex(int index, int data) {
        linknode cur = head;
        linknode node = new linknode(data);
        if (index == 0) {        //位置在最前面就头插法
            addFirst(data);
        }
        if (index == size()) {   //位置在末尾就尾插法
            addLast(data);
        }
        while (index != 0) {     //找到要插入节点的位置
            cur = cur.next;
            index--;
        }
        node.next = cur;         //实现链接
        cur.prve.next = node;
        node.prve = cur.prve;
        cur.prve = node;
    }

🌟这里要注意的是在插入位置的判断，位置在最前面就头插法，最后面接尾插法，在中间就要找到要插入的位置，最后实现链接。

💡💡图解如下：

🎥2.4删除第一次出现的key值

代码如下：

//删除第一次出现关键字为key的节点
    public void remove(int key) {
        linknode cur = head;
        if (head.val == key) {   //判断头结点是否满足
            head = head.next;
            head.prve = null;
            return;
        }

        while (cur.next != null) {  //循环遍历中间节点，除最后一个节点
            if (cur.val == key) {
                cur.prve.next = cur.next;
                cur.next.prve = cur.prve;
                return;
            }
            cur = cur.next;
        }
        if (cur.val == key) {    //单独处理最后一个节点
            last = cur.prve;
            last.next = null;
        }
    }

🌟首先判断头结点是否满足，如果满足就直接跳出去，如果不满足，就循环遍历cur节点，如果出现了key值，那么就直接跳过这个节点

注意：因为在跳过节点时，要通过next去指向地址，如果是最后一个节点，就会报空指针异常，所以只能到最后一个节点就跳出，那么就要单独处理最后一个节点。💡💡💡💡💡💡

🎥2.5删除所有key节点

代码如下：

public void removeAllKey(int key) {

        while (head.val == key && head != last) { //从前到倒数第二个节点判断。
            head = head.next;
            head.prve = null;
        }
        if (head.val == key) {   //单独处理最后一个节点
            head = null;
            last = null;
            return;
        }
        linknode cur = head;
        while (cur.next != null) {
            if (cur.val == key) {
                cur.prve.next = cur.next;
                cur.next.prve = cur.prve;
            }
            cur = cur.next;
        }
        if (cur.val == key) {
            last = cur.prve;
            last.next = null;
        }
    }

🌟与上一个代码基本一致，在实现删除后就不要return了。

💡💡💡💡注意：在头结点满足key之后，就要往后移，但是重复出现与值域key相同的时候，head又要往后移，并且将前驱智为空。当然还要单独处理最后一个满足key节点，这是属于全为key的极端条件。

🎥2.6打印以及求链表长度

~~~🥳🥳相信读到这里的uu，下面的代码岂不是小儿科！！！

代码如下：

public int size() {
        int index = 0;
        linknode cur = head;
        if (head == null) {   //判断链表是否为空
            return 0;
        }
        while (cur != null) {  //循环遍历链表
            cur = cur.next;
            index++;           //每遍历一个节点，就加一
        }     
        return index;
    }

    public void display() {    
        linknode cur = head;
        while (cur != null) {   //遍历每个链表，实现val值域的打印
            System.out.print(cur.val + " ");
            cur = cur.next;
        }
    }

🌟这里小编就不再赘述了，大家看看注解吧😊😊😊

📚️3.LinkedList的使用

~~~这部分就是比较实用的了，也很简单😊😊😊

1. LinkedList实现了List接口

2. LinkedList的底层使用了双向链表

3. LinkedList 没有实现RandomAccess接口，因此LinkedList不支持随机访问（这里就是，链表只能遍历找到元素，而顺序表，数组就能通过索引找到任意元素）

4. LinkedList的插入删除，增添的的时间复杂度为O（1），所以效率更高，更适合插入，增添的操作，顺序表适合查找的操作。

🎥3.1LinkedList的构造

代码如下

 LinkedList<Integer> list1 = new LinkedList<>();
 list1.add(1);


 List<String> list2 = new java.util.ArrayList<>();  //使用ArrayList构造linkedList
 list2.add("JavaSE");                               //也可使用add方法

🌟其实小编觉得就和实例化对象差不多~~~

🎥3.2LinkedList的其他方法✔️✔️✔️✔️

这里小编要说明一下：addAll

 LinkedList<Integer> list1 = new LinkedList<>();  //链表一
        list1.add(1);
        list1.add(2);
 List<Integer> list2 = new LinkedList<>();   //链表二
        list2.add(1);
        list2.add(2);
        list2.addAll(list1);                //尾插链表一
        System.out.println(list2);

输出：

[1,2,1,2]

💡💡就是在addAll的括号里加另一个链表，然后将这个链表加在本链表尾巴上就可以了。

当然还有以下：

boolean contains(Object o) 判断 o 是否在线性表中 int indexOf(Object o) 返回第一个 o 所在下标 int lastIndexOf(Object o) 返回最后一个 o 的下标 List<E> subList(int fromIndex, int toIndex) //别忘了左闭右开 截取部分list

🎥3.3linkedList的遍历

代码如下：

// foreach遍历
for (int e:list) {              //增强循环
     System.out.print(e + " ");
}

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

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

输出：