【Java演示】什么是链表？数据结构（三）链表：随机存储，顺序访问（读取）

链表：随机存储，顺序访问（读取）

前言

大家好，我是爱做梦的鱼，我是一个大三的小菜鸡，非常向往优秀，羡慕优秀的人，已拿两个暑假offer，欢迎大家找我进行交流????????????
这是我的博客地址：子浩的博客https://blog.csdn.net/weixin_43124279

专栏《两周干掉数据结构》

本博文的大部分插图来自于《漫画算法——小灰》，也复制了该书部分文字
我加了一些自己的总结、代码（我代码实现是参考了本书以及java自带LinkedList的源代码）
我发现本书有关链表的代码存在错误，已经向作者反馈
建议有能力的同学直接去看java自带LinkedList的源代码，写的真的好
应本书作者要求，加上本书公众号《程序员小灰》二维码

一、单向链表

链表（linked list）是一种在物理上非连续、非顺序的数据结构，由若干节点（node）所组成。
单向 链表的每一个节点又包含两部分，一部分是存放数据的变量data，另一部分是指向下一个节点的指针next。
链表的第1个节点被称为头节点，最后1个节点被称为尾节点，尾节点的next指针指向空。

什么叫随机存储呢？

如果说数组在内存中的存储方式是顺序存储，那么链表在内存中的存储方式则是随机存储 。
上一节我们讲解了数组的内存分配方式，数组在内存中占用了连续完整的存储空间。而链表则采用了见缝插针的方式，链表的每一个节点分布在内存的不同位置，依靠next指针关联起来。这样可以灵活有效地利用零散的碎片空间。

图中的箭头代表链表节点的next指针。

链表的基本操作

1. 查找节点

在查找元素时，链表不像数组那样可以通过下标快速进行定位，只能从头节点开始向后一个一个节点逐一查找。

/**
     * 链表查找元素
     *
     * @param index 查找的位置
     * @return index位置的Node对象
     */
    public Node get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表的节点的范围！");
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

链表中的数据只能按顺序进行访问，最坏的时间复杂度是O(n)

2. 更新节点

如果不考虑查找节点的过程，链表的更新过程会像数组那样简单，直接把旧数据替换成新数据即可。
如果不考虑查找元素的过程，只考虑纯粹的更新节点操作，时间复杂度是O(1)

/**
     * 更新节点 将列表中指定位置的节点的data替换为指定的data。
     *
     * @param index 需要更新的节点的位置
     * @param data  新data
     * @return 旧data
     */
    public int set(int index, int data) {
        Node x = get(index);
        int oldVal = x.data;
        x.data = data;
        return oldVal;
    }

3. 插入节点

只要内存空间允许，能够插入链表的元素是无穷无尽的，不需要像数组那样考虑扩容的问题。

与数组类似，链表插入节点时，同样分为3种情况。

• 尾部插入
• 头部插入
• 中间插入

3.1. 尾部插入

尾部插入，是最简单的情况，把最后一个节点的next指针指向新插入的节点即可。

3.2. 头部插入

头部插入，可以分成两个步骤。

1. 第1步，把新节点的next指针指向原先的头节点。
2. 第2步，把新节点变为链表的头节点。
   

3.3. 中间插入

中间插入，同样分为两个步骤。

1. 第1步，新节点的next指针，指向插入位置的节点。
2. 第2步，插入位置前置节点的next指针，指向新节点。
   

三钟情况的代码合到一起

/**
     * 链表插入元素
     *
     * @param index 插入位置
     * @param data  插入元素 被插入的链表节点的数据
     */
    public void insert(int index, int data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node insertedNode = new Node(data);
        if (size == 0) {
            //空链表
            head = insertedNode;
            last = insertedNode;
        } else if (index == 0) {
            //插入头部
            insertedNode.next = head;
            head = insertedNode;
        } else if (size == index) {
            //插入尾部
            last.next = insertedNode;
            last = insertedNode;
        } else {
            //插入中间
            Node prvNode = get(index - 1);
            insertedNode.next = prvNode.next;
            prvNode.next = insertedNode;
        }
        size++;
    }

4. 删除元素

链表的删除操作同样分为3种情况。

1. 尾部删除
2. 头部删除
3. 中间删除

4.1. 尾部删除

尾部删除，是最简单的情况，把倒数第2个节点的next指针指向空即
可。

4.1. 头部删除

头部删除，也很简单，把链表的头节点设为原先头节点的next指针即可。

4.1. 中间删除

中间删除，同样很简单，把要删除节点的前置节点的next指针，指向要
删除元素的下一个节点即可。

这里需要注意的是，许多高级语言，如Java，拥有自动化的垃圾回收机制，所以我们不用刻意去释放被删除的节点，只要没有外部引用指向它们，被删除的节点会被自动回收。
如果不考虑插入、删除操作之前查找元素的过程，只考虑纯粹的插入和删除操作，时间复杂度都是O(1)

/**
     * 链表删除元素
     *
     * @param index 删除的位置
     * @return 被删除的节点
     */
    public Node remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node removeNode;
        if (index == 0) {
            if (size == 0) {
                throw new NullPointerException("当前链表为空，不可以进行删除操作");
            }
            //删除头节点
            removeNode = head;
            head = head.next;
        } else if (index == size - 1) {
            //删除尾节点
            Node preNode = get(index - 1);
            removeNode = preNode.next;
            preNode.next = null;
            last = preNode;
        } else {
            //删除中间节点
            Node prevNode = get(index - 1);
            removeNode = prevNode.next;
            prevNode.next = prevNode.next.next;
        }
        size--;
        return removeNode;
    }

Java实现链表的完整代码

package chapter2.part2;

/**
 * Created by IntelliJ IDEA.
 *
 * @Author: 张志浩  Zhang Zhihao
 * @Email: 3382885270@qq.com
 * @Date: 2020/5/3
 * @Time: 13:39
 * @Version: 1.0
 */
public class MyLinkedList2 {
    private Node head; //头节点
    private Node last; //尾节点
    private int size; //链表实际长度

    public static void main(String[] args) {
        MyLinkedList2 myLinkedList = new MyLinkedList2();
//        myLinkedList.remove(0); // java.lang.NullPointerException: 当前链表为空，不可以进行删除操作
//        myLinkedList.remove(3); // java.lang.IndexOutOfBoundsException: 超出链表节点范围
        myLinkedList.insert(0, 3);
        myLinkedList.insert(1, 7);
        myLinkedList.insert(2, 9);
        myLinkedList.insert(3, 5);
        myLinkedList.insert(1, 6);
        myLinkedList.remove(0);
        myLinkedList.set(0, 23);
        myLinkedList.output();
    }

    /**
     * 链表插入元素
     *
     * @param index 插入位置
     * @param data  插入元素 被插入的链表节点的数据
     */
    public void insert(int index, int data) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围！");
        }
        Node insertedNode = new Node(data);
        if (size == 0) {
            //空链表
            head = insertedNode;
            last = insertedNode;
        } else if (index == 0) {
            //插入头部
            insertedNode.next = head;
            head = insertedNode;
        } else if (size == index) {
            //插入尾部
            last.next = insertedNode;
            last = insertedNode;
        } else {
            //插入中间
            Node prvNode = get(index - 1);
            insertedNode.next = prvNode.next;
            prvNode.next = insertedNode;
        }
        size++;
    }

    /**
     * 链表删除元素
     *
     * @param index 删除的位置
     * @return 被删除的节点
     */
    public Node remove(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表节点范围");
        }
        Node removeNode;
        if (index == 0) {
            if (size == 0) {
                throw new NullPointerException("当前链表为空，不可以进行删除操作");
            }
            //删除头节点
            removeNode = head;
            head = head.next;
        } else if (index == size - 1) {
            //删除尾节点
            Node preNode = get(index - 1);
            removeNode = preNode.next;
            preNode.next = null;
            last = preNode;
        } else {
            //删除中间节点
            Node prevNode = get(index - 1);
            removeNode = prevNode.next;
            prevNode.next = prevNode.next.next;
        }
        size--;
        return removeNode;
    }

    /**
     * 更新节点 将列表中指定位置的节点的data替换为指定的data。
     *
     * @param index 需要更新的节点的位置
     * @param data  新data
     * @return 旧data
     */
    public int set(int index, int data) {
        Node x = get(index);
        int oldVal = x.data;
        x.data = data;
        return oldVal;
    }

    /**
     * 链表查找元素
     *
     * @param index 查找的位置
     * @return index位置的Node对象
     */
    public Node get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出链表的节点的范围！");
        }
        Node temp = head;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }

    /**
     * 输出链表
     */
    public void output() {
        Node temp = head;
        while (temp != null) {
            System.out.print(temp.data + " ");
            temp = temp.next;
        }
    }

    /**
     * 链表节点
     */
    class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }
    }
}

二、双向链表

双向链表比单向链表稍微复杂一些，它的每一个节点除了拥有data和next指针，还拥有指向前置节点的prev 指针。

最后

以上就是精明百褶裙为你收集整理的【Java演示】什么是链表？数据结构（三）链表：随机存储，顺序访问（读取）的全部内容，希望文章能够帮你解决【Java演示】什么是链表？数据结构（三）链表：随机存储，顺序访问（读取）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。