一.简介：

1.链表是一种真正动态的数据结构

2.如果应用需要经常插入和删除元素使用链表将是很好的选择。

二.链表结构示意图

链表结构.jpg

• .链表中的元素在内存中不是顺序存储的，而是通过存在元素中的指针联系到一起，每个结点包括两个部分：一个是存储数据元素 的数据域，另一个是存储下一个结点地址的 指针。如果要访问链表中一个元素，需要从第一个元素始，一直找到需要元素位置。但是增加和删除一个元素对于链表数据结构就非常简单了，只要修改元素中的指针就可以

• .一般会有一个头指针head指向头结点，有时也会有尾指针tail，指向尾节点。

三.链表的代码实现

dummyHead链表实现.png

• 这个链表的实现中，使用了虚拟节点dummyHead，使添加操作add（）不在区分添加的是头结点还是其他节点，如果不使用dummyHead则需要判断添加的是不是头结点，因为头结点是没有上一个节点的。

/**
 * 添加了虚拟节点的链表，使得add()方法不需要对第一个节点特殊处理 
 * 链表时间复杂度分析： 增:O(n) 删:O(n) 改:O(n) 查:O(n)
 */
public class DummyLinkedList<E> {

  private int size;
  private Node dummyHead;

  public DummyLinkedList() {
    this.size = 0;
    this.dummyHead = new Node();
  }

  private class Node {

    public E e;
    public Node next;

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

    public Node(E e) {
      this(e, null);
    }

    public Node() {
      this(null, null);
    }

    @Override
    public String toString() {
      return e.toString();
    }
  }

  // 获取链表中的元素个数
  public int getSize() {
    return size;
  }

  // 返回链表是否为空
  public boolean isEmpty() {
    return size == 0;
  }

  /**
   * 在链表头添加新的元素e 时间复杂度O(1)
   */
  public void addFirst(E e) {
    add(0, e);
  }

  /**
   * 在链表的index(0-based)位置添加新的元素e 在链表中不是一个常用的操作，练习用：） 时间复杂度O(n/2)=O(n)
   */
  public void add(int index, E e) {
    if (index < 0 || index > size) {
      throw new IndexOutOfBoundsException();
    }
    if (index > 0 && isEmpty()) {
      throw new IndexOutOfBoundsException();
    }

    Node prevNode = dummyHead;
   /* 因为加了一个虚拟头结点，而使用者是不知道存在虚拟头结点的，
     所以使用者使用时的index指向的其实是用户想要添加的节点的上一个节点*/
    int i = 0;
    while (i < index) {
      prevNode = prevNode.next;
      i++;
    }
    prevNode.next = new Node(e, prevNode.next);
    size++;
  }

  /**
   * 在链表末尾添加新的元素e 时间复杂度O(n)
   */
  public void addLast(E e) {
    add(size, e);
  }

  /**
   * 根据底标获取一个元素 时间复杂度O(n/2)=O(n)
   */
  public E get(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
    Node node = dummyHead.next;
    for (int i = 0; i < index; i++) {
      node = node.next;
    }
    return node.e;
  }

  /**
   * 获得链表的第一个元素 时间复杂度O(1)
   */
  public E getFirst() {
    return get(0);
  }

  /**
   * 获得链表的最后一个元素 时间复杂度O(n)
   */
  public E getLast() {
    return get(size - 1);
  }

  /**
   * 修改index底标元素的值 时间复杂度O(n)
   */
  public void set(int index, E e) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
    Node node = dummyHead.next;
    for (int i = 0; i < index; i++) {
      node = node.next;
    }
    node.e = e;
  }

  /**
   * 查找链表中是否有元素e,时间复杂度O(n)
   */
  public boolean contains(E e) {
    Node node = dummyHead.next;
    while (node != null) {
      if (node.e.equals(e)) {
        return true;
      }
      node = node.next;
    }
    return false;
  }

  /**
   * 删除节点 时间复杂度O(n/2)=O(n)
   */
  public E remove(int index) {
    if (index < 0 || index >= size) {
      throw new IndexOutOfBoundsException();
    }
    Node prev = dummyHead;

    for (int i = 0; i < index; i++) {
      prev = prev.next;
    }
    Node cur = prev.next;
    prev.next = cur.next;
    cur.next = null;
    size--;
    return cur.e;
  }

  /**
   * 删除最后节点 时间复杂度O(n)
   */
  public E removeLast() {
    return remove(size - 1);
  }

  /**
   * 删除第一个节点 时间复杂度O(1)
   */
  public E removeFirst() {
    return remove(0);
  }

  @Override
  public String toString() {
    StringBuilder builder = new StringBuilder();
    Node cur;
    for (cur = dummyHead.next; cur != null; cur = cur.next) {
      builder.append(cur.e + "  ");
    }
    return builder.toString();
  }

  public static void main(String[] args) {

    DummyLinkedList<Integer> linkedList = new DummyLinkedList<>();
    for (int i = 0; i < 5; i++) {
      linkedList.addFirst(i);
      System.out.println(linkedList);
    }

    linkedList.add(2, 666);
    linkedList.remove(2);
    linkedList.removeFirst();
    linkedList.removeLast();
    System.out.println(linkedList);

  }
}

参考：

• 慕课网