# 链表

• 单向链表
• 双向链表

## 单向链表

``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;}@Overridepublic 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;``}``

## 双向链表

``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;}@Overridepublic 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``

1 声望

0 粉丝

0 条评论

• 单向链表
• 双向链表

## 单向链表

``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;}@Overridepublic 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;``}``

## 双向链表

``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;}@Overridepublic 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``