【数据结构】LinkedList与双向链表

我就是我 2023-09-27 13:24 112阅读 0赞

**目录**

一、认识集合类LinkedList

1、认识

2、构造方法

二、实现双向非循环链表

1、准备

2、方法的实现

1.遍历

2.有效节点个数

3.是否包含key

4.清空链表

5.头插法

6.尾插法

7.指定位置插入

8.删除第一次出现的key

9.删除所有的key

--------------------

##  ##

## 一、认识集合类LinkedList ##

### 1、认识 ###

LikedList类是List接口的实现类。他还实现了Deque接口，还是一个队列，也能当成双端队列来使用。虽然LinkedList是一个List集合，但是它的实现方式和ArrayList是完全不同的，ArrayList的底层是一个动态的Object\[\]数组，而LinkedList的底层是一个双向链表。

LinkedList是基于双向循环链表实现的，他还能当作队列或者栈来使用，他是线程不安全的，适合在单线程下使用

### 2、构造方法 ###

<table style="width:500px;"> 
 <tbody> 
  <tr> 
   <td>构造方法</td> 
   <td>说明</td> 
  </tr> 
  <tr> 
   <td>LinkedList()</td> 
   <td>无参构造</td> 
  </tr> 
  <tr> 
   <td>LinkedList(Collection&lt;? extends E&gt; c)</td> 
   <td>将指定集合转换为LinkedList，底层使用addAll方法</td> 
  </tr> 
 </tbody> 
</table>

## 二、实现双向非循环链表 ##

### 1、准备 ###

实现双向链表我们要先明白一个节点都有哪些字段，首先有存放数据的数据域，其次由于是双向的相对于单链表而言，增加了前驱节点

public class MyLinkedList {
        static class Node{
            public int val;     //数据域
            public Node prev;    //前驱指针
            public Node next;    //后驱指针
    
            /**
             * 构造节点
             * @param val
             */
            public Node(int val) {
                this.val = val;
            }
        }
    
        public Node head;    //作为头节点
        public Node last;    //作为尾节点
    }

### 2、方法的实现 ###

#### 1.遍历 ####

/**
         * 遍历双向链表
         */
        public void display(){
            Node cur = head;             //代替头节点遍历，跟单链表遍历相同
    
            while(cur != null){
                System.out.print(cur.val + " ");
            }
    
            System.out.println();
    
            cur = last;                 //代替尾节点遍历，反向遍历
            while(cur != null){
                System.out.print(cur.val + " ");
                cur = cur.prev;
            }
            System.out.println();
        }

#### 2.有效节点个数 ####

通过遍历时计算进行计数

/**
         * 计算节点个数
         * @return
         */
        public int size(){
            int size = 0;    //定义变量计数
            Node cur = head; //代替头指针遍历节点
    
            while(cur != null){
                size++;
                cur = cur.next;
            }
    
            return size;
        }

#### 3.是否包含key ####

通过遍历时判断是否存在

/**
         * 是否存在key
         * @param key  关键字
         * @return
         */
        public boolean contains(int key){
            Node cur = head;         //代替头节点遍历
    
            while(cur != null){     //开始遍历
                if(cur.val == key){ //如果存在返回
                    return true;
                }
                cur = cur.next;
            }
    
            return false;            //遍历完成后没有存在返回false
        }

#### 4.清空链表 ####

通过遍历释放每个节点的前驱与后驱指向

/**
         * 清空链表
         */
        public void clear(){
            Node cur = head;        //代替头节点进行遍历
    
            while(cur != null){
                Node next = cur.next;  //先记录下一个节点
                cur.next = null;      //释放前驱指向
                cur.prev = null;      //释放后驱指向
                cur = next;           //遍历下一个节点重复操作
            }
    
            head = null;             //释放头节点与尾节点
            last = null;
        }

#### 5.头插法 ####

在头插时，分两种清空，第一种是当前链表如果为空，此时插入数据是第一个只需让头指针与尾指针同时指向该节点，第二种情况是链表中已经有节点，此时插入时，分为三步：首先让新节点的next域指向头节点，然后让头节点的前驱指向新增节点，最后更新头节点的位置

![7e316779715942018a69e1bb101a8f7f.png][]

![3490b10b4b6f4b47816a2a33f03d8e81.png][]

/**
         * 头插法
         * @param data
         */
        public void addFirst(int data){
            Node node = new Node(data);   //构造节点
    
            if(head == null){
                //如果头节点为空，第一次插入，直接将头与尾指向新节点
                head = node;
                last = node;
            }else{
                //不是第一次插入
                node.next = head;    //此时新节点的next指向头节点
                head.prev = node;    //然后再将头节点的前驱指向新节点
                head = node;         //更新头节点的位置
            }
        }

#### 6.尾插法 ####

尾插时也分为两种情况，第一种是当前链表如果为空，此时插入数据是第一个只需让头指针与尾指针同时指向该节点，第二种情况是链表中已经有节点，此时插入时，分为三步：首先让新节点的前驱指向尾节点，然后让尾节点的next指向新增节点，最后更新尾节点的位置

![8ac09f786aee4d17a50ce3e91d250281.png][]

/**
         * 尾插法
         * @param data
         */
        public void addLast(int data){
            Node node = new Node(data);  //构造节点
    
            if(head == null){
                //如果头节点为空，第一次插入，直接将两个指针指向节点
                head = node;
                last = node;
            }else{
                //不是第一次插入
                last.next = node;  //将尾节点的next指向插入节点
                node.prev = last;  //再将插入节点的前驱节点指向尾节点
                last = node;       //更新尾节点的位置
            }
        }

#### 7.指定位置插入 ####

单链表里我们指定位置的插入要找到前驱节点，但是在双向链表里有前驱节点这个指针，我们只需要找到要求的下标的节点cur，找到后先将新增节点node.next指向cur，然后此处不能先将cur的前驱更改为node，因为如果更改了cur.prev我们在接前面的节点时就会失去地址，所以先将前面的节点与node连接node.prev = cur.prev（前一个节点的地址） cur.prev.next （前一个节点的next）= node

/**
         * 指定位置插入元素
         * @param index 指定下标
         * @param data  元素值
         */
        public void addIndex(int index,int data){
            //1.下标合法性判断 处理特殊情况
            if(index < 0 || index > size()){
                throw new ArrayIndexOutOfBoundsException("非法下标");
            }
    
            if(index == 0){
                addFirst(data);
                return;
            }
    
            if(index ==size()){
                addLast(data);
                return;
            }
    
            //2.找到当前节点
            Node cur = searchNodeToAdd(index);
    
            //3.开始插入
            Node node = new Node(data);
            node.next = cur;                //新增节点next指向当前节点
            node.prev = cur.prev;           //新增节点的前驱指向当前节点的前驱
            cur.prev.next = node;           //当前节点的前驱节点的next指向新增节点
            cur.prev = node;                //最后更新当前节点的前驱为新增节点
        }
    
        /**
         * 查找指定下标的节点
         * @param index
         * @return
         */
        private Node searchNodeToAdd(int index) {
            Node cur = head;
    
            while(index-- != 0){
                cur = cur.next;
            }
    
            return cur;
        }

#### 8.删除第一次出现的key ####

与单链表删除第一次出现的key类似，此处要处理前驱节点，核心步骤：找到节点cur，然后让cur的前面的节点的next指向cur.next，然后再让cur的后面的节点的前驱指向cur的前驱。要注意处理特殊情况：1.头节点 2.尾节点

/**
         * 删除第一次出现的key
         * @param key
         */
        public void remove(int key){
            Node cur = head;
    
            //直接遍历，遍历的时候找
            while(cur != null){
                if(cur.val == key){
                    if(cur == head){
                        //如果是头节点
                        head = head.next;
                        if(head != null){
                            //如果此时更新完头节点不为空就将新头的前驱置空
                            head.prev = null;
                        }
                    }else{
                        //不是头节点
                        cur.prev.next = cur.next;
                        if(cur == last){
                            //如果是最后一个节点更新last的位置
                            last = last.prev;
                        }else{
                            //不是最后一个节点正常删除
                            cur.next.prev = cur.prev;
                        }
                    }
                    //删除完成后返回
                    return;
                }
                cur = cur.next;
            }
        }

#### 9.删除所有的key ####

上述代码删除一个后就返回，也就是只删除第一个，如果我们删除第一个后继续删除满足条件的，我们只需去掉删除完成后的哪个return

/**
         * 删除所有的key
         * @param key 待删元素
         */
        public void removeAll(int key){
            Node cur = head;
    
            //直接遍历，遍历的时候找
            while(cur != null){
                if(cur.val == key){
                    if(cur == head){
                        //如果是头节点
                        head = head.next;
                        if(head != null){
                            //如果此时更新完头节点不为空就将新头的前驱置空
                            head.prev = null;
                        }
                    }else{
                        //不是头节点
                        cur.prev.next = cur.next;
                        if(cur == last){
                            //如果是最后一个节点更新last的位置
                            last = last.prev;
                        }else{
                            //不是最后一个节点正常删除
                            cur.next.prev = cur.prev;
                        }
                    }
                    //删除完成后不返回，继续执行
                }
                cur = cur.next;
            }
        }

[7e316779715942018a69e1bb101a8f7f.png]: https://img-blog.csdnimg.cn/7e316779715942018a69e1bb101a8f7f.png
[3490b10b4b6f4b47816a2a33f03d8e81.png]: https://img-blog.csdnimg.cn/3490b10b4b6f4b47816a2a33f03d8e81.png
[8ac09f786aee4d17a50ce3e91d250281.png]: https://img-blog.csdnimg.cn/8ac09f786aee4d17a50ce3e91d250281.png