链表由结点组成，每个结点除了保留本身的数据，还须要有指向其余结点的指针。与数组相比，链表在物理存储上是不间断的，不能通过下标进行随机拜访来获取元素。然而链表能够很容易的通过调整指针的指向实现减少和删除结点。
按指针的指向，链表分为：
- 单向链表
- 双向链表
单向链表
单向链表的结点只有一个指向下一个结点的指针。
先创立一个结点对象，蕴含一个指针属性next：
public class Node { private int data; private Node next; public Node() { } public Node(int data) { this.data = data; } public Node(Node next) { this.next = next; } public Node(int data, Node next) { this.data = data; this.next = next; } public int getData() { return data; } public void setData(int data) { this.data = data; } public Node getNext() { return next; } public void setNext(Node next) { this.next = next; } @Override public String toString() { return "Node{" + "data=" + data + '}'; }}将对单向链表的罕用操作封装到类中：
public class SingleLinkedList { /** * 遍历单向链表 * @param head 头结点 */ public void list(Node head) { if (head == null || head.getNext() == null) { System.out.println("the List is empty"); return; } Node temp = head.getNext(); while (true) { if (temp == null) { break; } System.out.println(temp); temp = temp.getNext(); } } /** * 获取单向链表长度（结点个数），不统计头结点 * @param head 头结点 * @return 返回链表长度（结点个数） */ public int getLength(Node head) { if (head == null || head.getNext() == null) { return 0; } Node temp = head.getNext(); int length = 0; while (temp != null) { length++; temp = temp.getNext(); } return length; } /** * 增加结点到单向链表的最初 * 1.找到以后单向链表的最初结点 * 2.将最初结点的next指向新结点 * @param head 头结点 * @param node */ public boolean add(Node head, Node node) { if (head == null || node == null) { return false; } Node temp = head; while (true) { if (temp.getNext() == null) { break; } temp = temp.getNext(); } temp.setNext(node); return true; } /** * 增加结点到指定结点前面 * @param node 指定的结点 * @param insertNode 增加的结点 */ public boolean insert(Node node, Node insertNode) { if (node == null || insertNode == null) { return false; } if (node.getNext() == null) { node.setNext(insertNode); return true; } insertNode.setNext(node.getNext()); node.setNext(insertNode); return true; } /** * 删除指定结点，须要找到指定结点的前一个结点 * @param deleteNode 删除的结点 */ public boolean delete(Node head, Node deleteNode) { if (head == null || deleteNode == null || head == deleteNode) { return false; } Node temp = head; while (true) { if (temp.getNext() == null) { return false; } if (temp.getNext() == deleteNode) { break; } temp = temp.getNext(); } temp.setNext(temp.getNext().getNext()); return true; }}进行测试：
public static void main(String[] args) { Node head = new Node(0); SingleLinkedList singleLinkedList = new SingleLinkedList(); Node node1 = new Node(1); Node node2 = new Node(2); Node node3 = new Node(3); Node node4 = new Node(4); System.out.println("===增加结点到最初==="); singleLinkedList.add(head,node1); singleLinkedList.add(head,node2); singleLinkedList.add(head,node3); singleLinkedList.add(head,node4); System.out.println("链表结点为："); singleLinkedList.list(head); System.out.println("链表长度为："); System.out.println(singleLinkedList.getLength(head)); System.out.println("===增加结点到指定结点前面==="); Node node5 = new Node(5); singleLinkedList.insert(node2,node5); System.out.println("链表结点为："); singleLinkedList.list(head); System.out.println("链表长度为："); System.out.println(singleLinkedList.getLength(head)); System.out.println("===删除指定结点==="); singleLinkedList.delete(head,node5); System.out.println("链表结点为："); singleLinkedList.list(head); System.out.println("链表长度为："); System.out.println(singleLinkedList.getLength(head)); }输入后果为：
===增加结点到最初===链表结点为：Node{data=1}Node{data=2}Node{data=3}Node{data=4}链表长度为：4===增加结点到指定结点前面===链表结点为：Node{data=1}Node{data=2}Node{data=5}Node{data=3}Node{data=4}链表长度为：5===删除指定结点===链表结点为：Node{data=1}Node{data=2}Node{data=3}Node{data=4}链表长度为：4反转单向链表
指定一个新的头结点，将每一个解决的结点都放在新的头结点之后。
/** * 反转单向链表 * @param head * @return */ public Node reverse(Node head) { if (head == null || head.getNext() == null) { return head; } // 指定一个新的头结点 Node newHead = new Node(0); // 指定以后解决的结点 Node curr = head.getNext(); // 指定以后解决结点的下一结点 Node next = null; while (curr != null) { // 第一步：获取反转前以后结点的下一结点 next = curr.getNext(); // 第二步：指定以后结点的下一结点为新的头结点的下一结点 curr.setNext(newHead.getNext()); // 第三步：指定新的头结点的下一结点为以后解决的结点 newHead.setNext(curr); // 持续解决后一个结点 curr = next; } // 指定原头结点的下一结点为新头结点的下一结点 head.setNext(newHead.getNext()); return head; }第一个结点解决示意图：
第二个结点解决示意图：
后面的循环遍历都没有思考单向列表成环的状况，如果有环的话，就会导致有限循环，能够通过快慢指针来查看环：
/** * 检测环 * @param head 头结点 * @return */ public boolean checkCircle(Node head) { if (head == null) { return false; } Node fast = head.getNext(); Node slow = head; while (fast != null && fast.getNext() != null) { fast = fast.getNext().getNext(); slow = slow.getNext(); if (slow == fast) { return true; } } return false; }双向链表
双向链表的结点有两个指针，别离指向上一个结点和下一个结点。
先创立一个结点对象，蕴含两指针属性pre和next：
public class DoubleNode { private int data; private DoubleNode pre; private DoubleNode next; public DoubleNode() { } public DoubleNode(int data) { this.data = data; } public DoubleNode(DoubleNode pre, DoubleNode next) { this.pre = pre; this.next = next; } public DoubleNode(int data, DoubleNode pre, DoubleNode next) { this.data = data; this.pre = pre; this.next = next; } public int getData() { return data; } public void setData(int data) { this.data = data; } public DoubleNode getPre() { return pre; } public void setPre(DoubleNode pre) { this.pre = pre; } public DoubleNode getNext() { return next; } public void setNext(DoubleNode next) { this.next = next; } @Override public String toString() { return "DoubleNode{" + "data=" + data + '}'; }}将对双向链表的罕用操作封装到类中：
public class DoubleLinkedList { /** * 遍历双向链表 * @param head 头结点 */ public void list(DoubleNode head) { if (head.getNext() == null) { System.out.println("the List is empty"); return; } DoubleNode temp = head.getNext(); while (true) { if (temp == null) { break; } System.out.println(temp); temp = temp.getNext(); } } /** * 获取双向链表长度（结点个数），不统计头结点 * @param head 头结点 * @return 返回链表长度（结点个数） */ public int getLength(DoubleNode head) { if (head == null || head.getNext() == null) { return 0; } DoubleNode temp = head.getNext(); int length = 0; while (temp != null) { length++; temp = temp.getNext(); } return length; } /** * 增加结点到双向链表的最初 * 1.找到以后双向链表的最初结点 * 2.将最初结点的next指向新结点 * 3.将新结点的pre指向前一结点 * @param head 头结点 * @param node 减少的结点 */ public void add(DoubleNode head, DoubleNode node) { DoubleNode temp = head; while (true) { if (temp.getNext() == null) { break; } temp = temp.getNext(); } temp.setNext(node); node.setPre(temp); } /** * 增加结点到指定结点前面 * @param node 指定的结点 * @param insertNode 增加的结点 */ public boolean insertAfter(DoubleNode node, DoubleNode insertNode) { if (node == null || insertNode == null) { return false; } if (node.getNext() == null) { node.setNext(insertNode); insertNode.setPre(node); return true; } insertNode.setPre(node); insertNode.setNext(node.getNext()); node.getNext().setPre(insertNode); node.setNext(insertNode); return true; } /** * 增加结点到指定结点后面 * @param node 指定的结点 * @param insertNode 增加的结点 */ public boolean insertBefore(DoubleNode node, DoubleNode insertNode) { if (node == null || insertNode == null) { return false; } if (node.getPre() == null) { insertNode.setNext(node); node.setPre(insertNode); return true; } insertNode.setPre(node.getPre()); insertNode.setNext(node); node.getPre().setNext(insertNode); node.setPre(insertNode); return true; } /** * 删除指定结点 * @param deleteNode 删除的结点 */ public boolean delete(DoubleNode deleteNode) { if (deleteNode == null) { return false; } if (deleteNode.getPre() != null){ deleteNode.getPre().setNext(deleteNode.getNext()); } if (deleteNode.getNext() != null) { deleteNode.getNext().setPre(deleteNode.getPre()); } return true; } /** * 检测环 * @param head 头结点 * @return */ public boolean checkCircle(DoubleNode head) { if (head == null) { return false; } DoubleNode fast = head.getNext(); DoubleNode slow = head; while (fast != null && fast.getNext() != null) { fast = fast.getNext().getNext(); slow = slow.getNext(); if (slow == fast) { return true; } } return false; }}进行测试：
public static void main(String[] args) { DoubleNode head = new DoubleNode(0); DoubleLinkedList doubleLinkedList = new DoubleLinkedList(); DoubleNode node1 = new DoubleNode(1); DoubleNode node2 = new DoubleNode(2); DoubleNode node3 = new DoubleNode(3); DoubleNode node4 = new DoubleNode(4); System.out.println("===增加结点到最初==="); doubleLinkedList.add(head,node1); doubleLinkedList.add(head,node2); doubleLinkedList.add(head,node3); doubleLinkedList.add(head,node4); System.out.println("链表结点为："); doubleLinkedList.list(head); System.out.println("链表长度为："); System.out.println(doubleLinkedList.getLength(head)); System.out.println("===增加结点到指定结点前面==="); DoubleNode node5 = new DoubleNode(5); doubleLinkedList.insertAfter(node2,node5); System.out.println("链表结点为："); doubleLinkedList.list(head); System.out.println("链表长度为："); System.out.println("===增加结点到指定结点后面==="); DoubleNode node6 = new DoubleNode(6); doubleLinkedList.insertBefore(node2,node6); System.out.println("链表结点为："); doubleLinkedList.list(head); System.out.println("链表长度为："); System.out.println(doubleLinkedList.getLength(head)); System.out.println("===删除指定结点==="); doubleLinkedList.delete(node5); System.out.println("链表结点为："); doubleLinkedList.list(head); System.out.println("链表长度为："); System.out.println(doubleLinkedList.getLength(head)); }输入后果为：
===增加结点到最初===链表结点为：DoubleNode{data=1}DoubleNode{data=2}DoubleNode{data=3}DoubleNode{data=4}链表长度为：4===增加结点到指定结点前面===链表结点为：DoubleNode{data=1}DoubleNode{data=2}DoubleNode{data=5}DoubleNode{data=3}DoubleNode{data=4}链表长度为：===增加结点到指定结点后面===链表结点为：DoubleNode{data=1}DoubleNode{data=6}DoubleNode{data=2}DoubleNode{data=5}DoubleNode{data=3}DoubleNode{data=4}链表长度为：6===删除指定结点===链表结点为：DoubleNode{data=1}DoubleNode{data=6}DoubleNode{data=2}DoubleNode{data=3}DoubleNode{data=4}链表长度为：5欢送关注我的公众号，一起学习。