算法与数据结构知识汇总（二、链表）

1、概念

链表，链式存储结构，是物理上不连续、逻辑上连续、可以动态添加和删除节点的数据结构。

节点的组成：数据域 + 指针域

链表分为：单链表、双链表、循环单链表。

本文以单项列表为例。

2、链表的数据结构

单向链表的数据结构如下图：

图片.png

上图数据结构为单向链表，简称单链表，该数据结构由若干个节点连接组成，链表中的数据在物理上不一定连续。

节点由两部分组成：数据（data） + 指针（next）

链表的元素由若干个节点组成，每个节点由数据和next组成。d1、d2、d3就是链表的数据，next指向下一个节点的地址。

3、单链表的Java实现

JDK的LinkedList集合代表链表，其代码实现如下：

    LinkedList<String> list = new LinkedList<>();
    //添加一个元素，默认在末尾添加一个元素
    list.add("张三");
    //在末尾添加一个元素
    list.addLast("张三");
    //在链表首部添加一个元素
    list.addFirst("张三");
    //在指定位置添加一个元素
    list.add(0, "张三");
    //移除某元素
    list.remove("张三");
    //删除一个元素，默认删除首部元素
    list.remove();
    //删除首部元素
    list.removeFirst();
    //删除尾部元素
    list.removeLast();
    //删除指定位置的元素
    list.remove(0);

链表常用于插入、删除数据较为频繁的场景。

研究一下链表的源码：

/**
 * Inserts the specified element at the specified position in this list.
 * Shifts the element currently at that position (if any) and any
 * subsequent elements to the right (adds one to their indices).
 *
 * @param index index at which the specified element is to be inserted
 * @param element element to be inserted
 * @throws IndexOutOfBoundsException {@inheritDoc}
 */
public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

add(int index, E element)在链表的指定位置添加一个元素，如果index正好等于链表的长度，那么就直接在链表的尾部添加一个元素，不需要消耗查找所需需要的时间，如果index不等于链表的长度，那么执行以下代码：

linkBefore(element, node(index));

下面来了重点知识，linkBefore方法的作用是将element插入到index位置上，在插入元素之前必须先找到index对应的节点，也就是linkBefore方法的第二个参数引用的方法：

/**
 * Returns the (non-null) Node at the specified element index.
 */
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

Node表示节点，通过for循环，从第一个元素或者最后一个元素开始查找，直到遍历到第index个节点为止。这就是链表的缺点，查询操作比较慢。

最终，根据等待插入的数据和index位置的节点开始插入操作。

/**
 * Inserts element e before non-null Node succ.
 */
void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);
    succ.prev = newNode;
    if (pred == null)
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

在这里，可以得出结论是，链表插入和删除数据不需要移动或拷贝元素，直接next 即可完成增加和删除操作，所以速度是比较快的，但是当在指定位置插入节点时，必须找到当前位置的节点，这个查询操作是非常的慢的，这是链表最主要的缺点了。

4、手写单链表

/**
 * 单链表
 */
public class SingleLinked<T> {

    private class Node{
        private T t;
        private Node next;
        public Node(T t,Node next){
            this.t = t;
            this.next = next;
        }
        public Node(T t){
            this(t,null);
        }
    }
    private Node head;          //头结点
    private int size;           //链表元素个数
    //构造函数
    public SingleLinked(){
        this.head = null;
        this.size = 0;
    }

    //获取链表元素的个数
    public int getSize(){
        return this.size;
    }
    //判断链表是否为空
    public boolean isEmpty(){
        return this.size == 0;
    }
    //链表头部添加元素
    public void addFirst(T t){
        Node node = new Node(t);    //节点对象
        node.next = this.head;
        this.head = node;
        this.size++;
        //this.head = new Node(e,head);等价上述代码
    }
    //向链表尾部插入元素
    public void addLast(T t){
        this.add(t, this.size);
    }
    //向链表中间插入元素
    public void add(T t,int index){
        if (index <0 || index >size){
            throw new IllegalArgumentException("index is error");
        }
        if (index == 0){
            this.addFirst(t);
        }
        Node preNode = this.head;
        //找到要插入节点的前一个节点
        for(int i = 0; i < index-1; i++){
            preNode = preNode.next;
        }
        Node node = new Node(t);
        //要插入的节点的下一个节点指向preNode节点的下一个节点
        node.next = preNode.next;
        //preNode的下一个节点指向要插入节点node
        preNode.next = node;
        this.size++;
    }
    //删除链表元素
    public void remove(T t){
        if(head == null){
            System.out.println("无元素可删除");
            return;
        }
        //要删除的元素与头结点的元素相同
        while(head != null && head.t.equals(t)){
            head = head.next;
            this.size--;
        }
        /**
         * 上面已经对头节点判别是否要进行删除
         * 所以要对头结点的下一个结点进行判别
         */
        Node cur = this.head;
        while(cur.next != null){
            if(cur.next.t.equals(t)){
                this.size--;
                cur.next = cur.next.next;
            }
            else cur = cur.next;
        }

    }
    //删除链表第一个元素
    public T removeFirst(){
        if(this.head == null){
            System.out.println("无元素可删除");
            return null;
        }
        Node delNode = this.head;
        this.head = this.head.next;
        delNode.next =null;
        this.size--;
        return delNode.t;
    }
    //删除链表的最后一个元素
    public T removeLast(){
        if(this.head == null){
            System.out.println("无元素可删除");
            return null;
        }
        //只有一个元素
        if(this.getSize() == 1){
            return this.removeFirst();
        }
        Node cur = this.head;   //记录当前结点
        Node pre = this.head;   //记录要删除结点的前一个结点
        while(cur.next != null){
            pre = cur;
            cur = cur.next;
        }
        pre.next = cur.next;
        this.size--;
        return cur.t;
    }
    //链表中是否包含某个元素
    public boolean contains(T t){
        Node cur = this.head;
        while(cur != null){
            if(cur.t.equals(t)){
                return true;
            }
            else cur = cur.next;
        }
        return false;
    }
    @Override
    public String toString() {
        StringBuffer sb = new StringBuffer();
        Node cur = this.head;
        while(cur != null){
            sb.append(cur.t+"->");
            cur = cur.next;
        }
        sb.append("NULL");
        return sb.toString();
    }

    public static void main(String[] args) {
        SingleLinked<Integer> linked = new SingleLinked();
        for(int i = 0; i < 10; i++){
            linked.addFirst(i);
            System.out.println(linked);
        }
        linked.addLast(33);
        linked.addFirst(33);
        linked.add(33, 5);
        System.out.println(linked);
        linked.remove(33);
        System.out.println(linked);
        System.out.println("删除第一个元素："+linked.removeFirst());
        System.out.println(linked);
        System.out.println("删除最后一个元素："+linked.removeLast());
        System.out.println(linked);
    }

}

5、手写双向链表

public class LinkedList<E> {

    /**
     * 结点
     * @param <E>
     */
    private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }


    Node<E> first;//头节点
    Node<E> last;//尾节点
    int size;//大小


    
    public LinkedList() {
    }

    /**
     * 在最后添加
     * @param e
     */
    public void add (E e) {
        linkLast(e);
    }

    /**
     * 在最后添加
     * @param e
     */
    private void linkLast(E e) {
        Node<E> newNode = new Node<E>(last, e, null);
        Node<E> l = last;

        last = newNode;

        if (l == null) {
            first = newNode;
        }else {
            l.next = newNode;
        }
        size ++;
    }

    /**
     * 获取第index位置上的节点的值域
     * @param index
     * @return
     */
    public E get(int index) {
        if(index < 0 || index >size) {
            return null;
        }
        return node(index).item;
    }

    /**
     * 获取第index位置上的节点
     * @param index
     * @return
     */
    private Node<E> node(int index) {
        //index在前半部份
        if (index < (size>>1)) {
            Node<E> node = first;
            for(int i = 0; i < index; i++) {
                node = node.next;
            }
            return node;
        } else { //index在后半部份
            Node<E> node = last;
            for(int i = size - 1; i > index; i--) {
                node = node.prev;
            }
            return node;
        }
    }

    /**
     * �在index的位置上添加一个元素
     * @param index
     * @param e
     */
    public void add (int index, E e) {
        if(index < 0 || index >size) {
            return;
        }
        if (index == size) {
            linkLast(e);
        } else {
            Node<E> target = node(index);
            Node<E> pre = target.prev;
            Node<E> newNode = new Node<E>(pre, e, target);

//          pre.next = newNode;
//          pre = newNode;
            //要考虑index=0时的情况
            if(pre == null) {
                first = newNode;
            } else {
                pre.next = newNode;
            }
            pre = newNode;
            size++;
        }
    }
    


    /**
     * @param index
     */
    public void remove(int index){
        Node<E> target = node(index);
        unlinkNode(target);
    }
    
    private void unlinkNode(Node<E> p) {
//      p.prev.next = p.next;
//      p.next.prev = p.prev;
        
        Node<E> pre = p.prev;
        Node<E> next = p.next;

        if (pre == null) {
            first = p.next;//删除头节点
        } else {
            pre.next = p.next;
        }

        if (next == null) {
            last = p.prev;//删除尾结节
        } else {
            next.prev = p.prev;
        }
        size--;
    }

}

6、顺序表和链表的比较

	顺序表	链表
优点	查找快	删除增加元素快
缺点	增删慢	查找慢

[完...]