数据结构之链表( 单链表, 双链表，循环链表)

冷不防 2023-02-13 08:46 4阅读 0赞

## 前篇、链表的概括 ##

#### 1、链表（Linked list）说明 ####

是一种常见的基础数据结构，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而顺序表相应的时间复杂度分别是O(logn)和O(1)。

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。

在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（“links”）。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的访问往往要在不同的排列顺序中转换。而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。链表有很多种不同的类型：单向链表，双向链表以及循环链表。

#### 2、理解方式 ####

基于链式存储结构的链表。你可以这样理解，比如说你要找一个人，名字叫张三，你首先跑到A，发现没有，A告诉你B可能知道，你跑到了B。B说C可能知道，你跑到了C，张三果然在C那里，如果没有就这样一直不停的去找。一张图看一下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70]

#### 3、历史 ####

链表开发于1955-56，由当时所属于兰德公司（英语：RAND Corporation）的艾伦纽维尔（Allen Newell），克里夫肖（Cliff Shaw）和赫伯特西蒙（Herbert Simon）在他们编写的信息处理语言（IPL）中做为原始数据类型所编写。IPL被作者们用来开发几种早期的人工智能程序，包括逻辑推理机，通用问题解算器和一个计算机象棋程序。

#### 4、java 底层链表的使用 ####

java中有很多集合类底层都是通过链表来实现的。而且面试的时候，链表的实现是经常考的一个知识点, 链表典型的使用就是 java.util 包下的集合LinkedList （如图）

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70 1]

## 一、单链表 ##

#### 1、描叙 ####

链表中最简单的一种是单向链表，它包含两个域，一个信息域和一个指针域。这个链接指向列表中的下一个节点，而最后一个节点则指向一个空值。

链表最基本的结构是在每个节点保存数据和到下一个节点的地址，在最后一个节点保存一个特殊的结束标记，另外在一个固定的位置保存指向第一个节点的指针，有的时候也会同时储存指向最后一个节点的指针。一般查找一个节点的时候需要从第一个节点开始每次访问下一个节点，一直访问到需要的位置。但是也可以提前把一个节点的位置另外保存起来，然后直接访问。当然如果只是访问数据就没必要了，不如在链表上储存指向实际数据的指针。这样一般是为了访问链表中的下一个或者前一个（需要储存反向的指针，见下面的双向链表）节点。

#### 2、图文示例 ####

一个单向链表的节点被分成两个部分。第一个部分保存或者显示关于节点的信息，第二个部分存储下一个节点的地址。单向链表只可向一个方向遍历。  
![在这里插入图片描述][20200530091730711.png]

#### 3、代码示例 ####

创建了一个单链表

**----实现了**  
尾部添加 (效率**高**)  
索引查询 (效率低)  
索引删除 (效率低)  
size 获取长度

**----未实现**  
头部添加数据  
中间添加数据  
索引更新数据  
等等

package linkedList;
    
    /**
     * TODO  单链表
     *
     * @author ws
     * @mail 1720696548@qq.com
     * @date 2020/5/27 0027 14:45
     */
    public class LinkedList {
    
        /**
         * 头节点
         */
        private Node head;
        /**
         * 尾节点
         */
        private Node tail;
        /**
         * 长度
         */
        private int size;
    
        /**
         * 添加元素到结尾处
         *
         * @param data
         */
        public void plus(Object data) {
            if (head == null) {
                // 第一个，也是最后一个
                head = new Node(data);
                tail = head;
            } else {
                tail.next = new Node(data);
                tail = tail.next;
            }
            size++;
        }
    
    
        /**
         * 根据索引获取元素,查询速度慢
         *
         * @param index
         */
        public Object get(int index) {
            this.checkElementIndex(index);
            return this.getNode(index).data;
        }
    
        /**
         * 删除元素, 把删除的上一个元素的下一个元素, 指向要删除的下一个元素, 当索引为0时，把下一个元素设置为头元素
         *
         * @param index
         */
        public Object remove(int index) {
            this.checkElementIndex(index);
            Node delNode = null;
            if (index == 0) {
                // 要删除的元素
                delNode = getNode(index);
                // 下一个元素
                Node nextNode = delNode.next;
                this.head = nextNode;
            } else {
                // 要删除的上一个元素
                Node preNode = getNode(index - 1);
                // 要删除的元素
                delNode = preNode.next;
                // 下一个元素
                Node nextNode = delNode.next;
                // 赋值
                preNode.setNext(nextNode);
            }
            Object data = delNode.data;
            // 赋空，让jvm回收
            delNode = null;
            size--;
            // 删除
            return data;
        }
    
    
        /**
         * 获取链表长度
         */
        public int getSize() {
            return size;
        }
    
        /**
         * TODO 获取头元素
         */
        private Node getHead() {
            return head;
        }
    
        /**
         * TODO  根据索引获取节点,查询速度慢
         *
         * @param index
         */
        private Node getNode(int index) {
            this.checkElementIndex(index);
            //获取第一个节点, 循环获取下一个节点(依次 .next.next.next)
            Node node = head;
            if (head != null) {
                for (int i = 0; i < index; i++) {
                    node = node.next;
                }
            }
            return node;
        }
    
    
        /**
         * TODO    判断下标
         *
         * @param index
         * @return void
         * @date 2019/11/28 0028 9:37
         */
        private void checkElementIndex(int index) {
            if (index < 0 && index >= size) {
                throw new IndexOutOfBoundsException("下标越界!");
            }
        }
    
    
        /**
         * TODO  链表元素
         */
        class Node {
            //节点值
            private Object data;
            //当前节点的下一个元素
            private Node next;
    
            public void setNext(Node next) {
                this.next = next;
            }
    
            public Node(Object data) {
                this.data = data;
            }
        }

**测试代码**

public static void main(String[] args) {
    
            // 添加
            LinkedList linkedList = new LinkedList();
            linkedList.plus("1");
            linkedList.plus("2");
            linkedList.plus("3");
    
            // 获取链表数据方式 .next.next.next
    //        System.out.println(linkedList.getHead().getData());
    //        System.out.println(linkedList.getHead().getNext().getData());
    //        System.out.println(linkedList.getHead().getNext().getNext().getData());
    
            // 遍历链表--> 每次 get都要 .next.next.next 一层一层的查下去，所以查询速度非常忙
            for (int i = 0; i < linkedList.getSize(); i++) {
                System.out.println(linkedList.get(i));
            }
    
            // 删除
            System.out.println("删除了数据:" + linkedList.remove(0));
            // 遍历
            for (int i = 0; i < linkedList.getSize(); i++) {
                System.out.println(linkedList.get(i));
            }
        }
    }

## 二、双链表 (效果同 LinkedList) ##

#### 1、描叙 ####

双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以配合下面的其他链表的扩展使用。

由于另外储存了指向链表内容的指针，并且可能会修改相邻的节点，有的时候第一个节点可能会被删除或者在之前添加一个新的节点。这时候就要修改指向首个节点的指针。有一种方便的可以消除这种特殊情况的方法是在最后一个节点之后、第一个节点之前储存一个永远不会被删除或者移动的虚拟节点，形成一个下面说的循环链表。这个虚拟节点之后的节点就是真正的第一个节点。这种情况通常可以用这个虚拟节点直接表示这个链表，对于把链表单独的存在数组里的情况，也可以直接用这个数组表示链表并用第0个或者第-1个（如果编译器支持）节点固定的表示这个虚拟节点。

#### 2、图文示例 ####

“双向链表”或“双面链表”。每个节点有两个连接：一个指向前一个节点，（当此“连接”为第一个“连接”时，指向空值或者空列表）；而另一个指向下一个节点，（当此“连接”为最后一个“连接”时，指向空值或者空列表）  
![在这里插入图片描述][20200530092145935.png]

#### 3、代码示例 ####

创建一个双链表

**实现了**  
1、add 最后添加节点数据 (效率高)  
2、push 最前添加节点数据 (效率高)  
3、get 索引查询 (效率低)  
4、remove 索引删除 (效率低)  
5、size 获取长度

package linkedList;
    
    
    /**
     *  双链表
     *
     * @author ws
     * @mail 1720696548@qq.com
     * @date 2020/5/27 0027 14:45
     */
    public class XiJiaLinkedList<E> {
        /**
         * 长度
         */
        private int size = 0;
        /**
         * 第一个节点
         */
        private Node first;
        /**
         * 最后一个节点
         */
        private Node last;
    
    
        /**
         * TODO    获取长度
         *
         * @return int
         * @date 2019/11/28 0028 9:37
         */
        public int getSize() {
            return size;
        }
    
    
        /**
         * TODO 添加数据（在最后）
         *
         * @param e
         * @return void
         * @date 2019/11/28 0028 9:26
         */
        public void add(E e) {
            Node node = new Node();
            node.object = e;
            //如果没有上一个节点，首次添加为第一个节点
            if (first == null) {
                first = node;
            } else {
                // 当前节点的上一个节点为最后一个节点
                node.prev = last;
                // 上次最后一个节点的下一个节点为当前新添加节点
                last.next = node;
            }
            //当前新添加节点(最后)
            last = node;
            size++;
        }
    
    
        /**
         * TODO 添加数据（在最前）
         *
         * @param e
         * @return void
         * @date 2019/11/28 0028 9:26
         */
        public void push(E e) {
            Node node = new Node();
            node.object = e;
            node.prev = null;
            //判断是否存在第一个节点，存在则为当前节点的下一个节点, 并赋值上一个节点为当前节点
            if (first != null) {
                node.next = first;
                first.prev = node;
            }
            //首次添加最后节点=当前节点
            if (last == null) {
                last = node;
            }
            //第一个节点
            first = node;
            size++;
        }
    
    
        /**
         * TODO    查询
         *
         * @param index
         * @return java.lang.Object
         * @date 2019/11/28 0028 9:32
         */
        public Object get(int index) {
            checkElementIndex(index);
            return getNode(index).object;
        }
    
        /**
         * TODO    查询实现，依次 .next可以看出查询效率低
         *
         * @param index
         * @return LinkedList.XiJiaLinkedList<E>.Node
         * @date 2019/11/28 0028 9:34
         */
        private Node getNode(int index) {
            checkElementIndex(index);
            Node node = first;
            if (first != null) {
                //获取第一个节点
                for (int i = 0; i < index; i++) {
                    //获取下一个节点(依次 .next.next.next)
                    node = node.next;
                }
            }
            return node;
        }
    
    
        /**
         * TODO    删除
         *
         * @param index
         * @return void
         * @date 2019/11/28 0028 9:37
         */
        public E remove(int index) {
            checkElementIndex(index);
            //要删除的节点
            XiJiaLinkedList<E>.Node delNode = getNode(index);
            //获取删除元素的上下节点
            XiJiaLinkedList<E>.Node prevNode = delNode.prev;
            XiJiaLinkedList<E>.Node nextNode = delNode.next;
            if (prevNode == null) {
                //要删除的节点为头节点，下一个节点为头元素
                first = nextNode;
                first.prev = null;
            } else if (nextNode == null) {
                //要删除的节点为尾节点
                last = prevNode;
                last.next = null;
            } else {
                //中间的节点
                prevNode.next = nextNode;
                nextNode.prev = prevNode;
            }
            //GC回收
            Object obj = delNode.object;
            delNode = null;
            size--;
            return (E) obj;
        }
    
    
        /**
         * TODO    判断下标
         *
         * @param index
         * @return void
         * @date 2019/11/28 0028 9:37
         */
        private void checkElementIndex(int index) {
            if (index < 0 || index > size) {
                throw new IndexOutOfBoundsException("下标越界!");
            }
        }
    
    
        /**
         * TODO    Node节点对象
         *
         * @date 2019/11/28 0028 9:48
         * @return
         */
        private class Node {
            /**
             * 节点内容
             */
            private Object object;
            /**
             * 上一个节点
             */
            private Node prev;
            /**
             * 下一个节点
             */
            private Node next;
        }

**测试代码**

/**
         * @param args
         */
        public static void main(String[] args) {
            // TODO Auto-generated method stub
            XiJiaLinkedList<String> list = new XiJiaLinkedList<String>();
            list.add("张三");
            list.add("李四");
            list.add("王五");
            list.push("赵六");
            list.push("小七");
    
    
            System.out.println("------------删除之前-------------");
            /*System.out.println(list.first.object);
    		System.out.println(list.first.next.object);
    		System.out.println(list.first.next.next.object);*/
            for (int i = 0; i < list.getSize(); i++) {
                System.out.println(list.get(i));
            }
            System.out.println("------------删除了" + list.remove(2));
            System.out.println("------------删除之后-------------");
            for (int i = 0; i < list.getSize(); i++) {
                System.out.println(list.get(i));
            }
        }
    }

## 三、循环链表 ##

#### 1、描叙 ####

在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，你开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存， 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。  
指向整个列表的指针可以被称作访问指针。

循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大(详见下面实例代码)。当然，如果只会在最后插入数据（或者只会在之前），处理也是很容易的。

另外有一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。

#### 2、图文示例 ####

*  循环链表中第一个节点之前就是最后一个节点
 *  在一个 循环链表中, 首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现

![在这里插入图片描述][20200530092251355.png]

**本文到此结束，如果觉得有用，劳烦各位点赞关注一下呗，将不定时持续更新更多的内容…，感谢大家的观看！**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200530091057230.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200530090815746.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNDYzNjU1,size_16,color_FFFFFF,t_70
[20200530091730711.png]: https://img-blog.csdnimg.cn/20200530091730711.png
[20200530092145935.png]: https://img-blog.csdnimg.cn/20200530092145935.png
[20200530092251355.png]: https://img-blog.csdnimg.cn/20200530092251355.png