线性表之链表

1、概述

动态数组在创建时就需要指定数组的长度，而且在数组需要扩容时，还需要提前创建更长的数组，这就会造成空间的浪费，那么能不能在需要多少内存，就创建多少内存呢。使用链表就能做到这点。
链表是一种链式存储的线性表，所有元素的地址不一定是连续的，因为添加的元素是动态创建的。
下面看下链表的结构：

image.png

2、链表的接口设计

链表中一般会包含链表容量(size)、头结点（first）、节点（Node）。

image.png
链表中大部分接口和动态数组是一样了，所以就可以把相同的接口进行抽取，如果链表中的大部分接口和具体实现和动态数组中完全一样，我们就可以将相同的接口抽取到Base类中，分别让动态数组和链表继承即可。但是很明显，链表和动态数组中的实现不可能完全一样，所以可以将接口抽取到接口中，然后创建一个抽象基类，将相同实现的接口放在其中，不同的实现交由子类去实现。具体结构如下：
image.png
代码如下：
List接口

public interface List<E> {
    int size(); // 元素的数量

    boolean isEmpty(); // 元素是否为空

    boolean contains(E element); // 否包含某个元素

    void add(E element); // 添加元素到最后面

    void add(int index, E element); // 向index位置添加元素

    E get(int index); // 获取index位置的元素

    E set(int index, E element); // 设置index位置的元素

    E remove(int index); // 删除某个位置的元素

    E remove(E element); // 删除某个元素

    int indexOf(E element); // 获取某个元素的index

    void clear(); // 清空元素
}

抽象基类AbstractList

public abstract class AbstractList<E> implements List<E> {
    protected int size;

    /**
     * @return 返回数组中元素的个数
     */
    public int size() {
        return size;
    }

    /**
     * @return 数组是否为空
     */
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * @param element
     * @return 是否包含元素element
     */
    public boolean contains(E element) {
        return indexOf(element) != -1;
    }

    /**
     * 添加元素
     * 
     * @param element
     */
    public void add(E element) {
        add(size, element);
    }

    protected void checkIndexForAdd(int index) {
        if (index < 0 || index > size)
            throw new IndexOutOfBoundsException("index is " + index + " size is " + size);
    }

    protected void checkIndex(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("index is " + index + " size is " + size);
    }

    /**
     * 删除元素
     * 
     * @param element
     * @return
     */
    public E remove(E element) {
        return remove(indexOf(element));
    }
}

LinkedList

public class LinkedList<E> extends AbstractList<E> {
    private Node<E> first;
    private static class Node<E> {
        private E element;
        private Node<E> next;

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

    @Override
    public void add(int index, E element) {
        // TODO Auto-generated method stub

    }

    @Override
    public E get(int index) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E set(int index, E element) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public E remove(int index) {
        // TODO Auto-generated method stub
        return null;
    }

    @Override
    public int indexOf(E element) {
        // TODO Auto-generated method stub
        return 0;
    }

    @Override
    public void clear() {

    }

}

3、LinkedList的具体实现

3.1、清空元素clear()的实现

image.png

从上图可以看出只需要将first置成null，不再指向index为0的元素，在垃圾回收时就会先回收index=0的元素，那么index=1的元素就没有被引用，也会被回收，以此类推，所有元素就会被全部回收了。具体实现如下

@Override
public void clear() {
    first = null;
    size = 0;
}

3.2、添加元素add(int index, E element)

添加元素需要找到index位置前一个元素，让前一个元素的next指向添加的元素，添加的元素的next指向index位置的元素。

image.png
为了找到index位置的元素，只需要通过first.next去查找，查找的次数就是index的大小，实现如下方法：

/**
 * 查找位置为index的元素
 */
private Node<E> nodeIndex(int index) {
    checkIndex(index);
    Node<E> node = first;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

找到了前一个元素add就很简单了

@Override
public void add(int index, E element) {
    Node<E> preNode = nodeIndex(index - 1);
    preNode.next = new Node<>(element, preNode.next);
    index++;
}

注意：在对链表操作时，尤其注意边界的处理，上面添加方法在向index=0的位置添加时，调用nodeIndex()时传入的index为-1是会抛出异常的，所以需要对index=0的位置进行处理。

@Override
public void add(int index, E element) {
    checkIndexForAdd(index);
    if (index == 0) {
        first = new Node<E>(element, first) ;
    } else {
        Node<E> preNode = nodeIndex(index - 1);
        preNode.next = new Node<>(element, preNode.next);
    }
    size++;
}

3.3、删除元素remove(int index)

image.png

@Override
public E remove(int index) {
    checkIndex(index);
    Node<E> oldNode = first;
    if (index == 0) {
        first = first.next;
    } else {
        Node<E> preNode = nodeIndex(index - 1);
        oldNode = preNode.next;
        preNode.next = preNode.next.next;
    }
    size--;
    return oldNode.element;
}

和添加元素一样，需要注意index=0的情况。
全部代码如下：

public class LinkedList<E> extends AbstractList<E> {

    private Node<E> first;

    private static class Node<E> {
        private E element;
        private Node<E> next;

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

    @Override
    public void add(int index, E element) {
        checkIndexForAdd(index);
        if (index == 0) {
            first = new Node<E>(element, first);
        } else {
            Node<E> preNode = nodeIndex(index - 1);
            preNode.next = new Node<>(element, preNode.next);
        }
        size++;
    }

    /**
     * 查找位置为index的元素
     */
    private Node<E> nodeIndex(int index) {
        checkIndex(index);
        Node<E> node = first;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }
        return node;
    }

    @Override
    public E get(int index) {
        Node<E> node = nodeIndex(index);
        return node.element;
    }

    @Override
    public E set(int index, E element) {
        Node<E> node = nodeIndex(index);
        E old = node.element;
        node.element = element;
        return old;
    }

    @Override
    public E remove(int index) {
        checkIndex(index);
        Node<E> oldNode = first;
        if (index == 0) {
            first = first.next;
        } else {
            Node<E> preNode = nodeIndex(index - 1);
            oldNode = preNode.next;
            preNode.next = preNode.next.next;
        }
        size--;
        return oldNode.element;
    }

    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null)
                    return i;
                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element))
                    return i;
                node = node.next;
            }
        }
        return -1;
    }

    @Override
    public void clear() {
        first = null;
        size = 0;
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("size=" + size + " [");
        Node<E> node = first;
        for (int i = 0; i < size; i++) {
            sb.append(node.element);
            if (i != size - 1)
                sb.append(" , ");
            node = node.next;
        }
        sb.append("]");
        return sb.toString();
    }
}

4、虚拟头结点

在对链表删除、添加时都需要找到前一个节点，但是当删除、添加的位置是第一个位置时，就需要进行判断处理了，为了统一处理所有节点的逻辑，可以在最前增加一个虚拟头结点，来简化处理逻辑。

image.png

可以给原链表增加构造函数，在构造函数中初始化虚拟头结点。

public LinkedList2() {
    first = new Node<>(null, null);
}

增加头结点，需要修改如下几个方法：

4.1、add方法

@Override
public void add(int index, E element) {
    checkIndexForAdd(index);
//      if (index == 0) {
//          first = new Node<E>(element, first);
//      } else {
//          Node<E> preNode = nodeIndex(index - 1);
//          preNode.next = new Node<>(element, preNode.next);
//      }
    //修改如下：
    Node<E> preNode = index == 0 ? first : nodeIndex(index - 1);
    preNode.next = new Node<>(element, preNode.next);
    size++;
}

4.2、nodeIndex方法

private Node<E> nodeIndex(int index) {
    checkIndex(index);
//      Node<E> node = first;
    Node<E> node = first.next;
    for (int i = 0; i < index; i++) {
        node = node.next;
    }
    return node;
}

4.3、remove方法

public E remove(int index) {
    checkIndex(index);
//      Node<E> oldNode = first;
//      if (index == 0) {
//          first = first.next;
//      } else {
//          Node<E> preNode = nodeIndex(index - 1);
//          oldNode = preNode.next;
//          preNode.next = preNode.next.next;
//      }

    Node<E> oldNode = null;
    Node<E> preNode = index == 0 ? first : nodeIndex(index - 1);
    oldNode = preNode.next;
    preNode.next = preNode.next.next;
    size--;
    return oldNode.element;
}

4.4、indexOf方法

public int indexOf(E element) {
    if (element == null) {
        //Node<E> node = first;
                Node<E> node = first.next;
        for (int i = 0; i < size; i++) {
            if (node.element == null)
                return i;
            node = node.next;
        }
    } else {
        //Node<E> node = first;
                Node<E> node = first.next;
        for (int i = 0; i < size; i++) {
            if (element.equals(node.element))
                return i;
            node = node.next;
        }
    }
    return -1;
}