【Java】链表

• Z时代
• 2024-01-10
• 分类：技术分享

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;
}

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

链表由结点组成，每个结点除了保存自身的数据，还需要有指向其他结点的指针。与数组相比，链表在物理存储上是不连续的，不能通过下标进行随机访问来获取元素。但是链表可以很容易的通过调整指针的指向实现增加和删除结点。

按指针的指向，链表分为：

• 单向链表
• 双向链表

单向链表

单向链表的结点只有一个指向下一个结点的指针。

先创建一个结点对象，包含一个指针属性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

欢迎关注我的公众号，一起学习。

以上是 【Java】链表 的全部内容， 来源链接： utcz.com/a/113427.html