一、单链表简介 链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
二、链表特点
单个结点创建非常方便，普通的线性内存通常在创建的时候就需要设定数据的大小结点的删除非常方便，不需要像线性结构那样移动剩下的数据结点的访问方便，可以通过循环或者递归的方法访问到任意数据，但是平均的访问效率低于线性表三、单链表 单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。
四、单链表Java代码实现
public class SingleLinkList { private Node first;//头结点 private int size; public SingleLinkList() { this.first = null; } //表头插入 public void insertNode(Object data){ Node newFirst = new Node(data); //当前为空 if (size==0){ first = newFirst; }else { newFirst.next = first; first = newFirst; } size ++; } //表头删除 public Object deleteLink(){ Object data = first.data; first = first.next; size --; return data; } //查找节点元素 public Node findLink(Object object){ Node current = first; for (int i = 0; i < size; i++) { if (object.equals(current.data)){ return current; }else { current = current.next; } } return null; } //删除某个元素 public boolean delete(Object object){ Node current = first; Node previous = first; if (size==0){ return false; } while (!current.data.equals(object)){ //当next为null时则退出循环 if (current.next==null){ return false; } previous = current; current = current.next; } //如果找到了则删除 //需要判断是不是头结点,如果是头结点则删除头结点，size-- if (current==first){ first = current.next; size--; }else { previous.next = current.next; size--; } return true; } //打印链表 //显示节点信息 public void showList(){ if (size==0){ return; } Node cur = first; StringBuilder stringBuilder = new StringBuilder(); while (cur !=null){ if (cur.next==null) { stringBuilder.append(cur.data); }else { stringBuilder.append(cur.data + "===>"); } cur = cur.next; } System.out.println(stringBuilder.toString()); } static class Node{ private Object data; Node next; //链表的下一个节点 public Node(Object data) { this.data = data; } //打印该链结点的信息 public void displayNode(){ System.out.println("data:"+data); } } public boolean isEmpty(){ return size==0; } public static void main(String[] args) { SingleLinkList singleLink = new SingleLinkList(); singleLink.insertNode("lisi"); singleLink.insertNode("zhangsan"); singleLink.insertNode("wangwu"); singleLink.insertNode("zhaoliu"); singleLink.insertNode("likui"); singleLink.showList(); singleLink.delete("zhangsan"); singleLink.showList(); } }五、双向链表 双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。 六、双向链表Java实现
public class DoubleLinkedList { private int size; private Node head; //首 private Node tail; //尾 public DoubleLinkedList() { this.size = 0; this.head = null; this.tail = null; } public void addHeadNode(Node currentNode) { //如果刚好是队头那就把当前节点设置为队头好队尾 if (size == 0) { tail = currentNode; } else { //如果不是队头则需要把插入的node设置为队头，只要把next指向于源队头，并size++ head.previous = currentNode; } currentNode.next = head; head = currentNode; size++; } /** * 添加到队尾 * * @param currentNode */ public void addTailNode( Node currentNode) { //如果size为0那就把当前节点设置为队头和队尾 if (size == 0) { head = currentNode; } else { //如果size不为0则需要把插入的node设置为队尾，只要把源队尾的next指向当前Node，并size++ tail.next = currentNode; currentNode.previous = tail; } tail = currentNode; size++; } //删除队头 public boolean deleteHead() { if (size == 0) { return false; } if (head.next == null) { tail = null; } else { head.next.previous = head; } head = head.next; size--; return true; } //删除队尾 public boolean deleteTail() { if (size == 0) { return false; } if (tail.previous==null) { head =null; } else { tail.previous.next=null; } tail = tail.previous; return true; } public Node find(Object object){ if (size==0){ return null; } Node node = head; while (!node.data.equals(object)){ if (node.next==null){ return null; } node = node.next; } return node; } public void showList(){ if (size==0){ return; } Node cur = head; StringBuilder stringBuilder = new StringBuilder(); while (cur !=null){ if (cur.next==null) { stringBuilder.append(cur.data); }else { stringBuilder.append(cur.data + "===>"); } cur = cur.next; } System.out.println(stringBuilder.toString()); } static class Node { private Object data; private Node next; private Node previous; public Node(Object data) { this.data = data; } } public static void main(String[] args) { DoubleLinkedList doublePointLinkedList = new DoubleLinkedList(); doublePointLinkedList.addHeadNode(new Node("lisi")); doublePointLinkedList.addHeadNode(new Node("wangwu")); doublePointLinkedList.addHeadNode(new Node("zhangsan")); doublePointLinkedList.addHeadNode(new Node("zhaoliu")); doublePointLinkedList.addHeadNode(new Node("qianduoduo")); doublePointLinkedList.showList(); doublePointLinkedList.deleteHead(); doublePointLinkedList.showList(); doublePointLinkedList.addTailNode(new Node("libai")); doublePointLinkedList.showList(); } }链表的相交： 要求： 如果两个链表没有交点，返回 null. 在返回结果后，两个链表仍须保持原有的结构。 可假定整个链表结构中没有循环。 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。 解决方案： 1.两个长度分别为a和b，如果a>b则a先遍历a-b，然后一起遍历判断结点是否相等
public static Node getIntersectionNode(SingleLinkList singleLinkListA, SingleLinkList singleLinkListB) { int lena = 0; int lenb = 0; Node headA = singleLinkListA.first; Node headB = singleLinkListB.first; Node tempa = headA; Node tempb = headB; while (tempa != null) { lena++; tempa = tempa.next; } while (tempb != null) { lenb++; tempb = tempb.next; } tempa = headA; tempb = headB; if (lena > lenb) { for (int i = 0; i < lena - lenb; i++) { tempa = tempa.next; } } else { for (int i = 0; i < lenb - lena; i++) { tempb = tempb.next; } } while (tempa != null && tempb != null && tempa.data != tempb.data) { tempa = tempa.next; tempb = tempb.next; } return tempa; }测试：
public static void main(String[] args) { SingleLinkList singleLink = new SingleLinkList(); singleLink.insertNode("lisi"); singleLink.insertNode("zhangsan"); singleLink.insertNode("wangwu"); singleLink.insertNode("zhaoliu"); singleLink.insertNode("likui"); singleLink.showList(); SingleLinkList singleLink2 = new SingleLinkList(); singleLink2.insertNode("lisi"); singleLink2.insertNode("zhangsan"); singleLink2.insertNode("wangwu"); singleLink2.insertNode("zhaoliu"); singleLink2.insertNode("likui"); singleLink2.insertNode("wangliu"); singleLink2.insertNode("liusheng"); singleLink2.showList(); Node node = getIntersectionNode(singleLink,singleLink2); if (node!=null){ System.out.println(node.data); } likui判断链表是否有环: 解题思路：使用两个指针一个慢指针slow 一个快指针fast(移动2个位置)，如果存在环那么慢指针的值会和快指针相等（fast.data=slow.data），如果快指针走到next结点为空，那么就不存在环 代码实现：
public static boolean isLoop(Node head){ Node slow = head.next; Node fast = head.next.next; // 链表为空或者只有一个节点 if(slow == null || fast == null){ return false; } while(slow.next != null){ // 只有 两个节点，当然是不存在循环的 if(fast.next == null){ return false; } // 如果slow的数据域和fast的数据域相同，则表示有环 if(slow.data == fast.data){ return true; } // slow指针走一步，fast走两步 slow = slow.next; fast = fast.next.next; //如果fast走到最后为空，表示没有环 if(fast == null){ return false; } } return false; }测试结果：
Node head = new Node(0); Node a = new Node(1); Node b = new Node(2); Node c = new Node(3); Node d = new Node(4); Node e = new Node(5); Node f = new Node(6); head.next = a; a.next = b; b.next = c; c.next = d; d.next = e; e.next = f; f.next = d; System.out.println(isLoop(head)); true