Java数据结构之链表相关知识总结
链表是一种非常常用的数据结构，它有许多实际应用，比如链表可以用来实现栈、队列、散列表和图等数据结构。在Java语言中，链表的实现方式主要有单向链表、双向链表和循环链表。
单向链表
单向链表是一种链表结构，每个节点包含两个元素：节点值和一个指向下一个节点的引用。链表的头结点（第一个节点）不包含值，仅包含指向链表中第一个实际节点的引用。
单向链表的实现示例如下：
public class SingleLinkedList {
private Node head; // 头结点，不包含值
private int size; // 链表长度
// 内部类Node，封装链表节点的值和next引用
private class Node {
Object value; // 节点的值
Node next; // 指向下一个节点的引用
public Node(Object value) {
this.value = value;
}
}
// 在头部插入节点
public void addFirst(Object value) {
Node newNode = new Node(value);
newNode.next = head;
head = newNode;
size++;
}
// 在尾部插入节点
public void addLast(Object value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
} else {
Node current = head;
while (current.next != null) {
current = current.next;
}
current.next = newNode;
}
size++;
}
// 在指定位置插入节点
public void add(int index, Object value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
addFirst(value);
} else if (index == size) {
addLast(value);
} else {
Node newNode = new Node(value);
Node current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
size++;
}
}
// 删除头节点，返回删除的节点值
public Object removeFirst() {
if (head == null) {
throw new NoSuchElementException();
}
Object value = head.value;
head = head.next;
size--;
return value;
}
// 删除尾节点，返回删除的节点值
public Object removeLast() {
if (head == null) {
throw new NoSuchElementException();
}
if (head.next == null) {
Object value = head.value;
head = null;
size--;
return value;
}
Node current = head;
while (current.next.next != null) {
current = current.next;
}
Object value = current.next.value;
current.next = null;
size--;
return value;
}
// 删除指定位置的节点，返回删除的节点值
public Object remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
return removeFirst();
} else if (index == size - 1) {
return removeLast();
} else {
Node current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
Object value = current.next.value;
current.next = current.next.next;
size--;
return value;
}
}
// 获取链表长度
public int size() {
return size;
}
// 获取指定位置的节点值
public Object get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.value;
}
}
双向链表
双向链表是一种链表结构，每个节点包含三个元素：前一个节点的引用、节点值和下一个节点的引用。链表的头结点（第一个节点）和尾节点（最后一个节点）都存在。
双向链表的实现示例如下：
public class DoubleLinkedList {
private Node head; // 头结点，不包含值
private Node tail; // 尾节点，不包含值
private int size; // 链表长度
// 内部类Node，封装链表节点的值、prev引用和next引用
private class Node {
Object value; // 节点的值
Node prev; // 指向前一个节点的引用
Node next; // 指向下一个节点的引用
public Node(Object value) {
this.value = value;
}
}
// 在头部插入节点
public void addFirst(Object value) {
Node newNode = new Node(value);
if (head != null) {
head.prev = newNode;
} else {
tail = newNode;
}
newNode.next = head;
head = newNode;
size++;
}
// 在尾部插入节点
public void addLast(Object value) {
Node newNode = new Node(value);
if (head == null) {
head = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
}
tail = newNode;
size++;
}
// 在指定位置插入节点
public void add(int index, Object value) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
addFirst(value);
} else if (index == size) {
addLast(value);
} else {
Node newNode = new Node(value);
Node current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
newNode.next = current.next;
newNode.prev = current;
current.next.prev = newNode;
current.next = newNode;
size++;
}
}
// 删除头节点，返回删除的节点值
public Object removeFirst() {
if (head == null) {
throw new NoSuchElementException();
}
Object value = head.value;
head = head.next;
if (head != null) {
head.prev = null;
} else {
tail = null;
}
size--;
return value;
}
// 删除尾节点，返回删除的节点值
public Object removeLast() {
if (head == null) {
throw new NoSuchElementException();
}
Object value = tail.value;
tail = tail.prev;
if (tail != null) {
tail.next = null;
} else {
head = null;
}
size--;
return value;
}
// 删除指定位置的节点，返回删除的节点值
public Object remove(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
if (index == 0) {
return removeFirst();
} else if (index == size - 1) {
return removeLast();
} else {
Node current = head;
for (int i = 0; i < index - 1; i++) {
current = current.next;
}
Object value = current.next.value;
current.next = current.next.next;
current.next.prev = current;
size--;
return value;
}
}
// 获取链表长度
public int size() {
return size;
}
// 获取指定位置的节点值
public Object get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
Node current = head;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.value;
}
}
示例说明
示例一
SingleLinkedList list = new SingleLinkedList();
list.addFirst(1); // 在头部插入节点
list.addLast(3); // 在尾部插入节点
list.add(1, 2); // 在指定位置插入节点
System.out.println(list.size()); // 获取链表长度
System.out.println(list.get(0)); // 获取第一个节点的值
System.out.println(list.get(1)); // 获取第二个节点的值
System.out.println(list.get(2)); // 获取第三个节点的值
以上代码输出的结果是：
3
1
2
3
示例二
DoubleLinkedList list = new DoubleLinkedList();
list.addFirst(1); // 在头部插入节点
list.addLast(3); // 在尾部插入节点
list.add(1, 2); // 在指定位置插入节点
System.out.println(list.size()); // 获取链表长度
System.out.println(list.get(0)); // 获取第一个节点的值
System.out.println(list.get(1)); // 获取第二个节点的值
System.out.println(list.get(2)); // 获取第三个节点的值
以上代码输出的结果是：
3
1
2
3
以上就是Java数据结构之链表相关知识的总结，希望对大家有所帮助！
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：Java数据结构之链表相关知识总结 - Python技术站
微信扫一扫 
支付宝扫一扫 