转载

Java版-数据结构-链表

概要

之前我们分别学习了解了动态数组、栈、队列，其实他们的底层都是依托静态数组来实现的、只是通过我们定义的 resize 方法来动态扩容解决固定容量的问题，那么我们即将学习的链表，它其实是一种真正的动态数据结构。

介绍

链表是一种最简单的动态数据结构，它能够辅助组成其它的数据结构，链表中的元素可存储在内存中的任何地方（不需要连续的内存，这一点和我们的数组具有很大的区别，数组需要连续的内存），链表中的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址 串接在一起 。

存储链表的数据的我们一般称为 节点（Node） ，节点一般分为两部分，一部分存储我们真正的数据，而另外一部分存储的是下一个节点的引用地址。

class Node{
    private E e; // 存储的真正元素
    private Node next;  // 存储下一个node的引用地址(指向下一个node)
}

比如现在我们将元素A、B、C三个节点添加到链表中，示意图如下：

Java版-数据结构-链表

从图中节点 A 到节点 B 之间的箭头代表，节点 A 指向了节点 B （ NodeA.next = NodeB ），因为在实际业务中我们的链表长度不可能是无穷无尽的，基本上都是有限个节点，通常定义链表中的最后一个元素它的 next 存储的是 NULL （空），换句话说，如果在链表中，一个节点的 next 是空（ NULL ）的话，那么它一定是最后一个节点（对应我们图中的 C 节点）。

根据我们上面介绍的链表基本结构，下面我们用代码定义一下链表的基本骨架（这里我们引入了一个 虚拟的头结点 ，下面我们会作说明）

public class LinkedList<E> {
    /**
     * 虚拟的头结点
     */
    private Node dummyHead;
    /**
     * 链表中节点的个数
     */
    private int size;

    public LinkedList() {
        // 创建一个虚拟的头结点
        dummyHead = new Node();
    }


    // 节点定义
    private class Node {
        // 存储节点的元素
        public E e;
        // 存储下一个节点的地址
        public Node next;

        public Node() {

        }

        public Node(E e) {
            this.e = e;
        }

        public Node(E e, Node next) {
            this.e = e;
            this.next = next;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "e=" + e +
                    ", next=" + next +
                    '}';
        }
    }
}

后面我们对链表的添加节点、删除节点以及查询节点，代码实现都会基于这个基本骨架

向链表中添加节点

思路分析：

一般我们向链表中添加节点，基本思路：找到添加节点位置的前一个节点 preNode ，然后再改变链表的地址引用；由于链表的第一个节点也就是头结点没有前节点，此时我们为了操作方便，为链表新增了 不存储任何元素 的一个 虚拟的头结点 dummyHead （不是必须的，对用户来讲是不可见的），其实链表中真正的第一个节点是节点 A （ dummyHead.next ），这样我们就能保证了，链表中存储元素的节点都有前一个节点。

Java版-数据结构-链表

下面我们来看一下，如果现在有一个节点 D ，我们准备把它插入到节点 B 的位置，我们需要做哪些操作

第一步：我们首先要找到节点 B 的前一个节点，也就是节点 A

第二步：将新节点 D 的指向指到节点 B （ NodeD.next = NodeA.next ），然后再将节点 A 的指向，指到节点 D （ NodeA.next = NodeD ），这样我们的节点就能 串接起来了

Java版-数据结构-链表

代码实现：

/**
  * 向链表中指定位置插入节点（学习使用，真正插入不会指定索引）
  *
  * @param index 索引的位置
  * @param e 节点元素
  */
public void add(int index, E e) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }

    Node prev = dummyHead;

    // 找到index位置的前一个节点
    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }

    // 新建一个节点，进行挂接
    Node node = new Node(e);
    node.next = prev.next;
    prev.next = node;

    size++;
}

链表的遍历

进行链表遍历，我们需要从链表中真正的第一个元素开始，也就是 dummyHead.next

/**
  * 获取链表中index位置的元素
  *
  * @param index  索引的位置
  * @return  节点的元素
  */
public E get(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    return cur.e;
}

修改链表中元素

/**
  * 修改链表中index位置节点的元素
  *
  * @param index 索引的位置
  * @param e 节点的元素
  */
public void set(int index, E e) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }
    Node cur = dummyHead.next;
    for (int i = 0; i < index; i++) {
        cur = cur.next;
    }
    cur.e = e;
}

查找链表中是否包含某元素

/**
  * 查找链表中是否包含元素e
  *
  * @param e
  * @return
  */
public boolean contains(E e) {
    Node cur = dummyHead.next;
    while (cur != null) {
        if (cur.e.equals(e)) {
            return true;
        }
        cur = cur.next;
    }
    return false;
}

删除链表中的元素

Java版-数据结构-链表

在链表中删除元素，与在链表中添加元素有点类似

第一步：我们首先找到删除节点位置的前一个节点，我们用 prev 表示，被删除的节点我们用 delNode 表示

第二步：改变链表的引用地址： prev.next = delNode.next （等同于，将节点在链表中删除）

/**
  * 删除链表中index位置的节点
  *
  * @param index
  */
public void remove(int index) {
    if (index < 0 || index > size) {
        throw new IllegalArgumentException("不是有效的索引");
    }

    Node prev = dummyHead;

    for (int i = 0; i < index; i++) {
        prev = prev.next;
    }

    Node delNode = prev.next;
    prev.next = delNode.next;
    delNode.next = null;
    size--;
}

完整版代码GitHub仓库地址： Java版数据结构-链表欢迎大家【关注】和【 Star 】

至此笔者已经为大家带来了数据结构：静态数组、动态数组、栈、数组队列、循环队列、链表；接下来，笔者还会一一的实现其它常见的数组结构，大家一起加油!