【链表】 是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针(Pointer)。
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多， 但是查找一个节点或者访问特定编号的节点则需要O(n)的时间， 而顺序表相应的时间复杂度分别是O(㏒ n)和O(1)。 【单向链表】 是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始 一个节点包含两个域，一个信息域和一个指针域，指针域指向下一个节点，最后一个节点指向一个空值 单向链表有一个头节点，可以不存储任何信息，包含一个指向第一个节点的指针 特点: 1.访问节点速度慢，需要从头节点一次遍历链表 2.更新节点快，节点不需要移动，更改相应指针即可单向链表节点类定义如下：
public class Node{ AnyType element; Node next; }
要实现单向列表的相关操作，可定义类SingleLinkedList如下：
public class SingleLinkedList{ private static class Node { AnyType element; Node next; public Node(AnyType element){ this.element = element; } } private Node header = new Node (null); private int size = 0; public boolean isEmpty(){ return size==0; } public void makeEmpty(){ header = null; } public int size(){ return size; } /** * Get element by index * */ public AnyType get(int index){ return getNode(index).element; } /** * Add the element to the end of this list * */ public void add(AnyType element){ add(new Node (element)); } /** * Inserts the specified element at the specified position in this list * 插入逻辑： * 1.创建一个新节点 * 2.将原index节点的前一个节点的指针指向新节点 * 3.将新节点的指针指向index节点 * 4.插入后，新节点的位置为index * */ public void add(int index,AnyType element){ Node newNode = new Node (element); Node previous = getNode(index-1); //index节点 Node node = previous.next; //将原index节点的前一个节点的指针指向newNode previous.next = newNode; //将newNode的指针指向index节点 newNode.next = node; size++; } /** * Inserts the specified element at the specified position in this list * 删除逻辑： * 1.获得index节点的前一个节点previousNode * 2.获得index节点的后一个节点nextNode * 3.将previousNode的指针指向nextNode * */ public void remove(int index){ Node previous = getNode(index-1); Node next = previous.next.next; previous.next = next; size--; } /** * 定义此方法是为了便于测试 * */ public List getElements(){ if(isEmpty()){ return null; }else{ List elements = new ArrayList (); Node node = (Node ) header; while(node.next!=null){ node = node.next; elements.add(((Element)node.element).getValue()); } return elements; } } //private methods private Node getNode(int index){ if(isEmpty()){ throw new RuntimeException("List is empty"); } int i = 0; Node node = header; while(i<=index){ node = node.next; i++; } return node; } private void add(Node newNode){ Node node = header; while(node.next!=null){ node = node.next; } node.next = newNode; size++; } }
如何实现链表反向：
/** * 链表反向 * */ public void reverse(){ if(!isEmpty()){ reverse(header.next,header.next.next); } } private void reverse(Nodenode,Node nextNode){ if(nextNode.next!=null){ reverse(nextNode,nextNode.next); }else{ //如果该节点是表尾，那么用头节点指向此节点 header.next = nextNode; } //该节点的指针指向前一个节点P，并将节点P的指针设置为空 nextNode.next = node; node.next = null; }