1. 什么是链表

链表是线性表的一种。线性表就是字面意思，数据之间的关系被一条线所串联。

线性表又分为地址空间间断的和地址空间不间断两种。

如数组就是地址空间间断线性表，他们在内存中是一块间断的数据块，块与块之间紧挨着，就好比X轴上的[-1,0,1]的关系一样。

而链表则是地址空间不间断的线性表，他们在内存中不是间断的块，而是扩散在各处，而后通过一条蜿蜒的线串起来了。

以下就是比拟形象的形容了。

  • 地址空间间断线性表：

    | |||||

  • 地址空间不间断线性表

    ---------->------->--->------------>>

2. 链表特点

链表分为单链表和双链表。单链表就是只晓得下一个节点的地位(上图是单链表)，而双链表则能够晓得上一个和下一个节点的地位。

单链表上的每个节点蕴含两局部，一部分是链表节点上的数据，另一部分则是指向下一个节点的线（指针）。

双链表上的每个节点蕴含三局部，一部分是链表节点上的数据，一部分是指向下一个节点的线（指针），还有一部分则是指向上一个节点的线（指针）。

链表的基本操作

  • 新增节点：在结尾、两头和开端
  • 删除节点：在结尾、两头和结尾
  • 查问节点：查问第i个地位的节点数据

3. java实现（双链表）

public class LinkedList<E> implements List<E>, Queue<E>, Stack<E> {    private int size = 0;    private Node<E> head;    private Node<E> tail;    public LinkedList() {        tail = head = null;    }    @Override    public boolean isEmpty() {        return size() == 0;    }    @Override    public int size() {        return size;    }    @Override    public boolean add(E e) {        return offer(e);    }    @Override    public boolean remove(E e) {        Node<E> tmp = head;        int idx = 0;        while (tmp != null) {            if (tmp.e.equals(e)) {                remove(idx);                return true;            }            idx++;            tmp = tmp.next;        }        return false;    }    @Override    public boolean contains(E e) {        Node<E> tmp = head;        while (tmp != null) {            if (tmp.e.equals(e)) {                return true;            }            tmp = tmp.next;        }        return false;    }    @Override    public E get(int i) {        if (i > size) {            throw new IndexOutOfBoundsException("Index i " + i + "out of range " + size);        }        if (i == 0) {            return head.e;        }        if (i == size - 1) {            return tail.e;        }        Node<E> tmp = head;        for (int j = 0; j < i; j++) {            tmp = tmp.next;        }        return tmp.e;    }    @Override    public E remove(int i) {        if (i >= size) {            throw new IndexOutOfBoundsException("Index i " + i + "out of range " + size);        }        if (i == 0) {            return poll();        }        if (i == size - 1) {            return pop();        }        Node<E> tmp = head;        for (int j = 0; j < i; j++) {            tmp = tmp.next;        }        E e = tmp.next.e;        tmp.next.next.prev = tmp;        tmp.next = tmp.next.next;        return e;    }    @Override    public boolean add(E e, int i) {        if (i > size) {            throw new IndexOutOfBoundsException("Index i " + i + "out of range " + size);        }        Node<E> node = new Node<>(e);        if (i == size) {            return offer(e);        }        if (i == 0) {            node.next = head;            node.prev = null;            head = node;        } else {            Node<E> tmp = head;            for (int j = 0; j <= i; j++) {                tmp = tmp.next;            }            tmp.next = node;            node.prev = tmp;        }        size++;        return false;    }    @Override    public String toString() {        StringBuilder sb = new StringBuilder();        sb.append("LinkedList: { ");        Node<E> node = head;        while (node != null) {            sb.append(node.e).append("<->");            node = node.next;        }        sb.append("null }");        return sb.toString();    }    private static class Node<E> {        E e;        Node<E> next;        Node<E> prev;        public Node(E e) {            this.e = e;        }    }}

4. 数据结构系列代码地址

集体还实现了其余数据结构和算法，感兴趣的搭档能够到Github或博客上查看具体残缺代码和测试。

Github：https://github.com/bennetty74...

Bugkit blog：http://bugkit.cn 或 IP