链表(Linked List)

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列节点组成，这些节点不必在内存中相连。每个节点由数据部分Data和链部分Next，Next指向下一个节点，这样当添加或者删除时，只需要改变相关节点的Next的指向，效率很高。

//链表的节点
class Node<E> {

  E item;
  Node<E> next;

  Node(E element) {
    this.item = element;
    this.next = null;
  }
}

//定义好节点后，使用前一般是对头节点和尾节点进行初始化
//头节点和尾节点都为空 链表为空
Node<E> head = null;
Node<E> tail = null;

//空链表创建一个新节点
//创建一个新的节点 并让head指向此节点
head = new Node("nodedata1");
//让尾节点也指向此节点
tail = head;

//链表追加一个节点
tail.next = new Node("nodedata2");
tail = tail.next;

//顺序遍历链表
Node<String> current = head;
while (current != null) {
  System.out.println(current.item);
  current = current.next;
}

//倒序遍历链表主要用了递归的思想
static void printListRev(Node<String> head) {
  if (head != null) {
    printListRev(head.next);
    System.out.println(head.item);
  }
}

//单链表反转 主要是逐一改变两个节点间的链接关系来完成
static Node<String> revList(Node<String> head) {

  if (head == null) {
    return null;
  }

  Node<String> nodeResult = null;
  Node<String> nodePre = null;
  Node<String> current = head;

  while(current != null) {
    Node<String> nodeNext = current.next;
    if (nodeNext == null) {
      nodeResult = current;
    }

    current.next = nodePre;
    nodePre = current;
    current = nodeNext;
  }
  return nodeResult;
}

链表的实现还有其它的方式，常见的有循环单链表，双向链表，循环双向链表。 循环单链表 主要是链表的最后一个节点指向第一个节点，整体构成一个链环。 双向链表 主要是节点中包含两个指针部分，一个指向前驱元，一个指向后继元，JDK中LinkedList集合类的实现就是双向链表。 循环双向链表 是最后一个节点指向第一个节点。