双向链表(Doubly Linked List)
介绍
双向链表是链表的一种变体，其中每个节点包含三个部分：数据域、前向指针和后向指针。前向指针指向前一个节点，后向指针指向后一个节点。这种结构使得链表可以从两个方向进行遍历，增加了灵活性。
与单向链表相比，双向链表支持双向遍历，并且在某些操作上更高效，例如删除给定节点或在特定节点前插入新节点。双向链表的头结点的前向指针和尾节点的后向指针通常指向null，表示链表的边界。
核心特性
双向遍历：可以从前向后或从后向前遍历链表
两个指针：每个节点有指向前一个和后一个节点的指针
动态大小：可以根据需要动态增长和缩小
非连续存储：节点在内存中分散存储，通过指针相连
基本操作
1. 访问元素
时间复杂度：O(n)
说明：必须从头节点或尾节点开始遍历直到找到目标节点
2. 插入操作
头部插入：O(1)
尾部插入：O(1)
中间插入：O(n)查找位置 + O(1)插入操作
3. 删除操作
头部删除：O(1)
尾部删除：O(1)（如果维护了尾指针）
中间删除：O(n)查找位置 + O(1)删除操作
给定节点删除：O(1)，无需查找其前驱节点
4. 查找元素
时间复杂度：O(n)
可以根据查找目标的位置选择从头部或尾部开始查找
基础实现
代码实现
Java 实现
▼Java复制代码// 定义节点类
class Node {
int data; // 数据域
Node next; // 指向下一个节点的指针
Node prev; // 指向前一个节点的指针
// 构造函数
public Node(int data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
// 双向链表类
class DoublyLinkedList {
private Node head; // 头节点
private Node tail; // 尾节点
private int size; // 链表大小
// 构造函数，创建一个空链表
public DoublyLinkedList() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 判断链表是否为空
public boolean isEmpty() {
return head == null;
}
// 获取链表大小
public int size() {
return size;
}
// 在链表头部插入节点
public void insertAtHead(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
head = newNode;
tail = newNode;
} else {
newNode.next = head;
head.prev = newNode;
head = newNode;
}
size++;
}
// 在链表尾部插入节点
public void insertAtTail(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.prev = tail;
tail = newNode;
}
size++;
}
// 在指定位置插入节点
public void insertAtPosition(int data, int position) {
// 位置无效
if (position < 0 || position > size) {
System.out.println("位置无效");
return;
}
// 插入位置为0，相当于在头部插入
if (position == 0) {
insertAtHead(data);
return;
}
// 插入位置为size，相当于在尾部插入
if (position == size) {
insertAtTail(data);
return;
}
// 插入到中间位置
Node newNode = new Node(data);
// 判断从头部还是尾部遍历更快
if (position <= size / 2) {
// 从头部遍历
Node current = head;
for (int i = 0; i < position; i++) {
current = current.next;
}
// 在current之前插入新节点
newNode.prev = current.prev;
newNode.next = current;
current.prev.next = newNode;
current.prev = newNode;
} else {
// 从尾部遍历
Node current = tail;
for (int i = size - 1; i > position; i--) {
current = current.prev;
}
// 在current之前插入新节点
newNode.prev = current.prev;
newNode.next = current;
current.prev.next = newNode;
current.prev = newNode;
}
size++;
}
// 删除头节点
public void deleteHead() {
if (isEmpty()) {
System.out.println("链表为空，无法删除");
return;
}
if (head == tail) {
// 只有一个节点
head = null;
tail = null;
} else {
head = head.next;
head.prev = null;
}
size--;
}
// 删除尾节点
public void deleteTail() {
if (isEmpty()) {
System.out.println("链表为空，无法删除");
return;
}
if (head == tail) {
// 只有一个节点
head = null;
tail = null;
} else {
tail = tail.prev;
tail.next = null;
}
size--;
}
// 删除指定位置的节点
public void deleteAtPosition(int position) {
// 位置无效
if (position < 0 || position >= size) {
System.out.println("位置无效");
return;
}
// 删除头节点
if (position == 0) {
deleteHead();
return;
}
// 删除尾节点
if (position == size - 1) {
deleteTail();
return;
}
// 删除中间节点
// 判断从头部还是尾部遍历更快
if (position <= size / 2) {
// 从头部遍历
Node current = head;
for (int i = 0; i < position; i++) {
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
} else {
// 从尾部遍历
Node current = tail;
for (int i = size - 1; i > position; i--) {
current = current.prev;
}
current.prev.next = current.next;
current.next.prev = current.prev;
}
size--;
}
// 删除第一个值为data的节点
public void delete(int data) {
if (isEmpty()) {
System.out.println("链表为空，无法删除");
return;
}
// 删除的是头节点
if (head.data == data) {
deleteHead();
return;
}
// 删除的是尾节点
if (tail.data == data) {
deleteTail();
return;
}
// 删除的是中间节点
Node current = head.next;
while (current != null && current != tail) {
if (current.data == data) {
current.prev.next = current.next;
current.next.prev = current.prev;
size--;
return;
}
current = current.next;
}
System.out.println("未找到要删除的元素");
}
// 查找节点
public boolean search(int data) {
if (isEmpty()) {
return false;
}
Node current = head;
while (current != null) {
if (current.data == data) {
return true;
}
current = current.next;
}
return false;
}
// 从头到尾打印链表
public void displayForward() {
if (isEmpty()) {
System.out.println("链表为空");
return;
}
Node current = head;
System.out.print("null <- ");
while (current != null) {
System.out.print(current.data);
if (current.next != null) {
System.out.print(" <-> ");
} else {
System.out.print(" -> ");
}
current = current.next;
}
System.out.println("null");
}
// 从尾到头打印链表
public void displayBackward() {
if (isEmpty()) {
System.out.println("链表为空");
return;
}
Node current = tail;
System.out.print("null <- ");
while (current != null) {
System.out.print(current.data);
if (current.prev != null) {
System.out.print(" <-> ");
} else {
System.out.print(" -> ");
}
current = current.prev;
}
System.out.println("null");
}
}
// 使用示例
public class DoublyLinkedListDemo {
public static void main(String[] args) {
DoublyLinkedList list = new DoublyLinkedList();
list.insertAtTail(10);
list.insertAtTail(20);
list.insertAtTail(30);
list.insertAtHead(5);
System.out.println("从头到尾打印：");
list.displayForward(); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
System.out.println("从尾到头打印：");
list.displayBackward(); // 输出: null <- 30 <-> 20 <-> 10 <-> 5 -> null
list.insertAtPosition(15, 2);
System.out.println("插入15到位置2后：");
list.displayForward(); // 输出: null <- 5 <-> 10 <-> 15 <-> 20 <-> 30 -> null
list.delete(15);
System.out.println("删除15后：");
list.displayForward(); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
System.out.println("查找结果: " + list.search(20)); // 输出: 查找结果: true
System.out.println("链表长度: " + list.size()); // 输出: 链表长度: 4
list.deleteHead();
System.out.println("删除头节点后：");
list.displayForward(); // 输出: null <- 10 <-> 20 <-> 30 -> null
list.deleteTail();
System.out.println("删除尾节点后：");
list.displayForward(); // 输出: null <- 10 <-> 20 -> null
}
}
JavaScript 实现
▼Javascript复制代码// 定义节点类
class Node {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
// 双向链表类
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 0;
}
// 判断链表是否为空
isEmpty() {
return this.head === null;
}
// 获取链表大小
getSize() {
return this.size;
}
// 在链表头部插入节点
insertAtHead(data) {
const newNode = new Node(data);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
} else {
newNode.next = this.head;
this.head.prev = newNode;
this.head = newNode;
}
this.size++;
}
// 在链表尾部插入节点
insertAtTail(data) {
const newNode = new Node(data);
if (this.isEmpty()) {
this.head = newNode;
this.tail = newNode;
} else {
this.tail.next = newNode;
newNode.prev = this.tail;
this.tail = newNode;
}
this.size++;
}
// 在指定位置插入节点
insertAtPosition(data, position) {
// 位置无效
if (position < 0 || position > this.size) {
console.log("位置无效");
return;
}
// 插入位置为0，相当于在头部插入
if (position === 0) {
this.insertAtHead(data);
return;
}
// 插入位置为size，相当于在尾部插入
if (position === this.size) {
this.insertAtTail(data);
return;
}
// 插入到中间位置
const newNode = new Node(data);
// 判断从头部还是尾部遍历更快
if (position <= this.size / 2) {
// 从头部遍历
let current = this.head;
for (let i = 0; i < position; i++) {
current = current.next;
}
// 在current之前插入新节点
newNode.prev = current.prev;
newNode.next = current;
current.prev.next = newNode;
current.prev = newNode;
} else {
// 从尾部遍历
let current = this.tail;
for (let i = this.size - 1; i > position; i--) {
current = current.prev;
}
// 在current之前插入新节点
newNode.prev = current.prev;
newNode.next = current;
current.prev.next = newNode;
current.prev = newNode;
}
this.size++;
}
// 删除头节点
deleteHead() {
if (this.isEmpty()) {
console.log("链表为空，无法删除");
return;
}
if (this.head === this.tail) {
// 只有一个节点
this.head = null;
this.tail = null;
} else {
this.head = this.head.next;
this.head.prev = null;
}
this.size--;
}
// 删除尾节点
deleteTail() {
if (this.isEmpty()) {
console.log("链表为空，无法删除");
return;
}
if (this.head === this.tail) {
// 只有一个节点
this.head = null;
this.tail = null;
} else {
this.tail = this.tail.prev;
this.tail.next = null;
}
this.size--;
}
// 删除指定位置的节点
deleteAtPosition(position) {
// 位置无效
if (position < 0 || position >= this.size) {
console.log("位置无效");
return;
}
// 删除头节点
if (position === 0) {
this.deleteHead();
return;
}
// 删除尾节点
if (position === this.size - 1) {
this.deleteTail();
return;
}
// 删除中间节点
// 判断从头部还是尾部遍历更快
if (position <= this.size / 2) {
// 从头部遍历
let current = this.head;
for (let i = 0; i < position; i++) {
current = current.next;
}
current.prev.next = current.next;
current.next.prev = current.prev;
} else {
// 从尾部遍历
let current = this.tail;
for (let i = this.size - 1; i > position; i--) {
current = current.prev;
}
current.prev.next = current.next;
current.next.prev = current.prev;
}
this.size--;
}
// 删除第一个值为data的节点
delete(data) {
if (this.isEmpty()) {
console.log("链表为空，无法删除");
return;
}
// 删除的是头节点
if (this.head.data === data) {
this.deleteHead();
return;
}
// 删除的是尾节点
if (this.tail.data === data) {
this.deleteTail();
return;
}
// 删除的是中间节点
let current = this.head.next;
while (current !== null && current !== this.tail) {
if (current.data === data) {
current.prev.next = current.next;
current.next.prev = current.prev;
this.size--;
return;
}
current = current.next;
}
console.log("未找到要删除的元素");
}
// 查找节点
search(data) {
if (this.isEmpty()) {
return false;
}
let current = this.head;
while (current !== null) {
if (current.data === data) {
return true;
}
current = current.next;
}
return false;
}
// 从头到尾打印链表
displayForward() {
if (this.isEmpty()) {
console.log("链表为空");
return;
}
let result = "null <- ";
let current = this.head;
while (current !== null) {
result += current.data;
if (current.next !== null) {
result += " <-> ";
} else {
result += " -> ";
}
current = current.next;
}
result += "null";
console.log(result);
}
// 从尾到头打印链表
displayBackward() {
if (this.isEmpty()) {
console.log("链表为空");
return;
}
let result = "null <- ";
let current = this.tail;
while (current !== null) {
result += current.data;
if (current.prev !== null) {
result += " <-> ";
} else {
result += " -> ";
}
current = current.prev;
}
result += "null";
console.log(result);
}
}
// 使用示例
const list = new DoublyLinkedList();
list.insertAtTail(10);
list.insertAtTail(20);
list.insertAtTail(30);
list.insertAtHead(5);
console.log("从头到尾打印：");
list.displayForward(); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
console.log("从尾到头打印：");
list.displayBackward(); // 输出: null <- 30 <-> 20 <-> 10 <-> 5 -> null
list.insertAtPosition(15, 2);
console.log("插入15到位置2后：");
list.displayForward(); // 输出: null <- 5 <-> 10 <-> 15 <-> 20 <-> 30 -> null
list.delete(15);
console.log("删除15后：");
list.displayForward(); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
console.log("查找结果:", list.search(20)); // 输出: 查找结果: true
console.log("链表长度:", list.getSize()); // 输出: 链表长度: 4
list.deleteHead();
console.log("删除头节点后：");
list.displayForward(); // 输出: null <- 10 <-> 20 <-> 30 -> null
list.deleteTail();
console.log("删除尾节点后：");
list.displayForward(); // 输出: null <- 10 <-> 20 -> null
Python 实现
▼Python复制代码class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def is_empty(self):
return self.head is None
def get_size(self):
return self.size
def insert_at_head(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
else:
new_node.next = self.head
self.head.prev = new_node
self.head = new_node
self.size += 1
def insert_at_tail(self, data):
new_node = Node(data)
if self.is_empty():
self.head = new_node
self.tail = new_node
else:
self.tail.next = new_node
new_node.prev = self.tail
self.tail = new_node
self.size += 1
def insert_at_position(self, data, position):
# 位置无效
if position < 0 or position > self.size:
print("位置无效")
return
# 插入位置为0，相当于在头部插入
if position == 0:
self.insert_at_head(data)
return
# 插入位置为size，相当于在尾部插入
if position == self.size:
self.insert_at_tail(data)
return
# 插入到中间位置
new_node = Node(data)
# 判断从头部还是尾部遍历更快
if position <= self.size // 2:
# 从头部遍历
current = self.head
for i in range(position):
current = current.next
# 在current之前插入新节点
new_node.prev = current.prev
new_node.next = current
current.prev.next = new_node
current.prev = new_node
else:
# 从尾部遍历
current = self.tail
for i in range(self.size - 1, position, -1):
current = current.prev
# 在current之前插入新节点
new_node.prev = current.prev
new_node.next = current
current.prev.next = new_node
current.prev = new_node
self.size += 1
def delete_head(self):
if self.is_empty():
print("链表为空，无法删除")
return
if self.head == self.tail:
# 只有一个节点
self.head = None
self.tail = None
else:
self.head = self.head.next
self.head.prev = None
self.size -= 1
def delete_tail(self):
if self.is_empty():
print("链表为空，无法删除")
return
if self.head == self.tail:
# 只有一个节点
self.head = None
self.tail = None
else:
self.tail = self.tail.prev
self.tail.next = None
self.size -= 1
def delete_at_position(self, position):
# 位置无效
if position < 0 or position >= self.size:
print("位置无效")
return
# 删除头节点
if position == 0:
self.delete_head()
return
# 删除尾节点
if position == self.size - 1:
self.delete_tail()
return
# 删除中间节点
# 判断从头部还是尾部遍历更快
if position <= self.size // 2:
# 从头部遍历
current = self.head
for i in range(position):
current = current.next
current.prev.next = current.next
current.next.prev = current.prev
else:
# 从尾部遍历
current = self.tail
for i in range(self.size - 1, position, -1):
current = current.prev
current.prev.next = current.next
current.next.prev = current.prev
self.size -= 1
def delete(self, data):
if self.is_empty():
print("链表为空，无法删除")
return
# 删除的是头节点
if self.head.data == data:
self.delete_head()
return
# 删除的是尾节点
if self.tail.data == data:
self.delete_tail()
return
# 删除的是中间节点
current = self.head.next
while current is not None and current != self.tail:
if current.data == data:
current.prev.next = current.next
current.next.prev = current.prev
self.size -= 1
return
current = current.next
print("未找到要删除的元素")
def search(self, data):
if self.is_empty():
return False
current = self.head
while current is not None:
if current.data == data:
return True
current = current.next
return False
def display_forward(self):
if self.is_empty():
print("链表为空")
return
result = "null <- "
current = self.head
while current is not None:
result += str(current.data)
if current.next is not None:
result += " <-> "
else:
result += " -> "
current = current.next
result += "null"
print(result)
def display_backward(self):
if self.is_empty():
print("链表为空")
return
result = "null <- "
current = self.tail
while current is not None:
result += str(current.data)
if current.prev is not None:
result += " <-> "
else:
result += " -> "
current = current.prev
result += "null"
print(result)
# 使用示例
if __name__ == "__main__":
linked_list = DoublyLinkedList()
linked_list.insert_at_tail(10)
linked_list.insert_at_tail(20)
linked_list.insert_at_tail(30)
linked_list.insert_at_head(5)
print("从头到尾打印：")
linked_list.display_forward() # 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
print("从尾到头打印：")
linked_list.display_backward() # 输出: null <- 30 <-> 20 <-> 10 <-> 5 -> null
linked_list.insert_at_position(15, 2)
print("插入15到位置2后：")
linked_list.display_forward() # 输出: null <- 5 <-> 10 <-> 15 <-> 20 <-> 30 -> null
linked_list.delete(15)
print("删除15后：")
linked_list.display_forward() # 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
print(f"查找结果: {linked_list.search(20)}") # 输出: 查找结果: True
print(f"链表长度: {linked_list.get_size()}") # 输出: 链表长度: 4
linked_list.delete_head()
print("删除头节点后：")
linked_list.display_forward() # 输出: null <- 10 <-> 20 <-> 30 -> null
linked_list.delete_tail()
print("删除尾节点后：")
linked_list.display_forward() # 输出: null <- 10 <-> 20 -> null
Go 实现
▼Go复制代码package main
import "fmt"
// 定义节点结构体
type Node struct {
data int
next *Node
prev *Node
}
// 双向链表结构体
type DoublyLinkedList struct {
head *Node
tail *Node
size int
}
// 创建新链表
func NewDoublyLinkedList() *DoublyLinkedList {
return &DoublyLinkedList{nil, nil, 0}
}
// 判断链表是否为空
func (list *DoublyLinkedList) IsEmpty() bool {
return list.head == nil
}
// 获取链表大小
func (list *DoublyLinkedList) Size() int {
return list.size
}
// 在链表头部插入节点
func (list *DoublyLinkedList) InsertAtHead(data int) {
newNode := &Node{data: data, next: nil, prev: nil}
if list.IsEmpty() {
list.head = newNode
list.tail = newNode
} else {
newNode.next = list.head
list.head.prev = newNode
list.head = newNode
}
list.size++
}
// 在链表尾部插入节点
func (list *DoublyLinkedList) InsertAtTail(data int) {
newNode := &Node{data: data, next: nil, prev: nil}
if list.IsEmpty() {
list.head = newNode
list.tail = newNode
} else {
list.tail.next = newNode
newNode.prev = list.tail
list.tail = newNode
}
list.size++
}
// 在指定位置插入节点
func (list *DoublyLinkedList) InsertAtPosition(data int, position int) {
// 位置无效
if position < 0 || position > list.size {
fmt.Println("位置无效")
return
}
// 插入位置为0，相当于在头部插入
if position == 0 {
list.InsertAtHead(data)
return
}
// 插入位置为size，相当于在尾部插入
if position == list.size {
list.InsertAtTail(data)
return
}
// 插入到中间位置
newNode := &Node{data: data, next: nil, prev: nil}
// 判断从头部还是尾部遍历更快
if position <= list.size/2 {
// 从头部遍历
current := list.head
for i := 0; i < position; i++ {
current = current.next
}
// 在current之前插入新节点
newNode.prev = current.prev
newNode.next = current
current.prev.next = newNode
current.prev = newNode
} else {
// 从尾部遍历
current := list.tail
for i := list.size - 1; i > position; i-- {
current = current.prev
}
// 在current之前插入新节点
newNode.prev = current.prev
newNode.next = current
current.prev.next = newNode
current.prev = newNode
}
list.size++
}
// 删除头节点
func (list *DoublyLinkedList) DeleteHead() {
if list.IsEmpty() {
fmt.Println("链表为空，无法删除")
return
}
if list.head == list.tail {
// 只有一个节点
list.head = nil
list.tail = nil
} else {
list.head = list.head.next
list.head.prev = nil
}
list.size--
}
// 删除尾节点
func (list *DoublyLinkedList) DeleteTail() {
if list.IsEmpty() {
fmt.Println("链表为空，无法删除")
return
}
if list.head == list.tail {
// 只有一个节点
list.head = nil
list.tail = nil
} else {
list.tail = list.tail.prev
list.tail.next = nil
}
list.size--
}
// 删除指定位置的节点
func (list *DoublyLinkedList) DeleteAtPosition(position int) {
// 位置无效
if position < 0 || position >= list.size {
fmt.Println("位置无效")
return
}
// 删除头节点
if position == 0 {
list.DeleteHead()
return
}
// 删除尾节点
if position == list.size-1 {
list.DeleteTail()
return
}
// 删除中间节点
// 判断从头部还是尾部遍历更快
if position <= list.size/2 {
// 从头部遍历
current := list.head
for i := 0; i < position; i++ {
current = current.next
}
current.prev.next = current.next
current.next.prev = current.prev
} else {
// 从尾部遍历
current := list.tail
for i := list.size - 1; i > position; i-- {
current = current.prev
}
current.prev.next = current.next
current.next.prev = current.prev
}
list.size--
}
// 删除第一个值为data的节点
func (list *DoublyLinkedList) Delete(data int) {
if list.IsEmpty() {
fmt.Println("链表为空，无法删除")
return
}
// 删除的是头节点
if list.head.data == data {
list.DeleteHead()
return
}
// 删除的是尾节点
if list.tail.data == data {
list.DeleteTail()
return
}
// 删除的是中间节点
current := list.head.next
for current != nil && current != list.tail {
if current.data == data {
current.prev.next = current.next
current.next.prev = current.prev
list.size--
return
}
current = current.next
}
fmt.Println("未找到要删除的元素")
}
// 查找节点
func (list *DoublyLinkedList) Search(data int) bool {
if list.IsEmpty() {
return false
}
current := list.head
for current != nil {
if current.data == data {
return true
}
current = current.next
}
return false
}
// 从头到尾打印链表
func (list *DoublyLinkedList) DisplayForward() {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}
result := "null <- "
current := list.head
for current != nil {
result += fmt.Sprintf("%d", current.data)
if current.next != nil {
result += " <-> "
} else {
result += " -> "
}
current = current.next
}
result += "null"
fmt.Println(result)
}
// 从尾到头打印链表
func (list *DoublyLinkedList) DisplayBackward() {
if list.IsEmpty() {
fmt.Println("链表为空")
return
}
result := "null <- "
current := list.tail
for current != nil {
result += fmt.Sprintf("%d", current.data)
if current.prev != nil {
result += " <-> "
} else {
result += " -> "
}
current = current.prev
}
result += "null"
fmt.Println(result)
}
func main() {
list := NewDoublyLinkedList()
list.InsertAtTail(10)
list.InsertAtTail(20)
list.InsertAtTail(30)
list.InsertAtHead(5)
fmt.Println("从头到尾打印：")
list.DisplayForward() // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
fmt.Println("从尾到头打印：")
list.DisplayBackward() // 输出: null <- 30 <-> 20 <-> 10 <-> 5 -> null
list.InsertAtPosition(15, 2)
fmt.Println("插入15到位置2后：")
list.DisplayForward() // 输出: null <- 5 <-> 10 <-> 15 <-> 20 <-> 30 -> null
list.Delete(15)
fmt.Println("删除15后：")
list.DisplayForward() // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
fmt.Printf("查找结果: %t
", list.Search(20)) // 输出: 查找结果: true
fmt.Printf("链表长度: %d
", list.Size()) // 输出: 链表长度: 4
list.DeleteHead()
fmt.Println("删除头节点后：")
list.DisplayForward() // 输出: null <- 10 <-> 20 <-> 30 -> null
list.DeleteTail()
fmt.Println("删除尾节点后：")
list.DisplayForward() // 输出: null <- 10 <-> 20 -> null
}
C 实现
▼C复制代码#include
#include
#include
// 定义节点结构
typedef struct Node {
int data;
struct Node* next;
struct Node* prev;
} Node;
// 定义链表结构
typedef struct {
Node* head;
Node* tail;
int size;
} DoublyLinkedList;
// 创建新链表
DoublyLinkedList* createList() {
DoublyLinkedList* list = (DoublyLinkedList*)malloc(sizeof(DoublyLinkedList));
if (list == NULL) {
printf("内存分配失败
");
exit(1);
}
list->head = NULL;
list->tail = NULL;
list->size = 0;
return list;
}
// 判断链表是否为空
bool isEmpty(DoublyLinkedList* list) {
return list->head == NULL;
}
// 获取链表大小
int size(DoublyLinkedList* list) {
return list->size;
}
// 创建新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败
");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
newNode->prev = NULL;
return newNode;
}
// 在链表头部插入节点
void insertAtHead(DoublyLinkedList* list, int data) {
Node* newNode = createNode(data);
if (isEmpty(list)) {
list->head = newNode;
list->tail = newNode;
} else {
newNode->next = list->head;
list->head->prev = newNode;
list->head = newNode;
}
list->size++;
}
// 在链表尾部插入节点
void insertAtTail(DoublyLinkedList* list, int data) {
Node* newNode = createNode(data);
if (isEmpty(list)) {
list->head = newNode;
list->tail = newNode;
} else {
list->tail->next = newNode;
newNode->prev = list->tail;
list->tail = newNode;
}
list->size++;
}
// 在指定位置插入节点
void insertAtPosition(DoublyLinkedList* list, int data, int position) {
// 位置无效
if (position < 0 || position > list->size) {
printf("位置无效
");
return;
}
// 插入位置为0，相当于在头部插入
if (position == 0) {
insertAtHead(list, data);
return;
}
// 插入位置为size，相当于在尾部插入
if (position == list->size) {
insertAtTail(list, data);
return;
}
// 插入到中间位置
Node* newNode = createNode(data);
// 判断从头部还是尾部遍历更快
if (position <= list->size / 2) {
// 从头部遍历
Node* current = list->head;
for (int i = 0; i < position; i++) {
current = current->next;
}
// 在current之前插入新节点
newNode->prev = current->prev;
newNode->next = current;
current->prev->next = newNode;
current->prev = newNode;
} else {
// 从尾部遍历
Node* current = list->tail;
for (int i = list->size - 1; i > position; i--) {
current = current->prev;
}
// 在current之前插入新节点
newNode->prev = current->prev;
newNode->next = current;
current->prev->next = newNode;
current->prev = newNode;
}
list->size++;
}
// 删除头节点
void deleteHead(DoublyLinkedList* list) {
if (isEmpty(list)) {
printf("链表为空，无法删除
");
return;
}
Node* temp = list->head;
if (list->head == list->tail) {
// 只有一个节点
list->head = NULL;
list->tail = NULL;
} else {
list->head = list->head->next;
list->head->prev = NULL;
}
free(temp);
list->size--;
}
// 删除尾节点
void deleteTail(DoublyLinkedList* list) {
if (isEmpty(list)) {
printf("链表为空，无法删除
");
return;
}
Node* temp = list->tail;
if (list->head == list->tail) {
// 只有一个节点
list->head = NULL;
list->tail = NULL;
} else {
list->tail = list->tail->prev;
list->tail->next = NULL;
}
free(temp);
list->size--;
}
// 删除指定位置的节点
void deleteAtPosition(DoublyLinkedList* list, int position) {
// 位置无效
if (position < 0 || position >= list->size) {
printf("位置无效
");
return;
}
// 删除头节点
if (position == 0) {
deleteHead(list);
return;
}
// 删除尾节点
if (position == list->size - 1) {
deleteTail(list);
return;
}
// 删除中间节点
Node* current;
// 判断从头部还是尾部遍历更快
if (position <= list->size / 2) {
// 从头部遍历
current = list->head;
for (int i = 0; i < position; i++) {
current = current->next;
}
} else {
// 从尾部遍历
current = list->tail;
for (int i = list->size - 1; i > position; i--) {
current = current->prev;
}
}
current->prev->next = current->next;
current->next->prev = current->prev;
free(current);
list->size--;
}
// 删除第一个值为data的节点
void deleteNode(DoublyLinkedList* list, int data) {
if (isEmpty(list)) {
printf("链表为空，无法删除
");
return;
}
// 删除的是头节点
if (list->head->data == data) {
deleteHead(list);
return;
}
// 删除的是尾节点
if (list->tail->data == data) {
deleteTail(list);
return;
}
// 删除的是中间节点
Node* current = list->head->next;
while (current != NULL && current != list->tail) {
if (current->data == data) {
current->prev->next = current->next;
current->next->prev = current->prev;
free(current);
list->size--;
return;
}
current = current->next;
}
printf("未找到要删除的元素
");
}
// 查找节点
bool search(DoublyLinkedList* list, int data) {
if (isEmpty(list)) {
return false;
}
Node* current = list->head;
while (current != NULL) {
if (current->data == data) {
return true;
}
current = current->next;
}
return false;
}
// 从头到尾打印链表
void displayForward(DoublyLinkedList* list) {
if (isEmpty(list)) {
printf("链表为空
");
return;
}
printf("null <- ");
Node* current = list->head;
while (current != NULL) {
printf("%d", current->data);
if (current->next != NULL) {
printf(" <-> ");
} else {
printf(" -> ");
}
current = current->next;
}
printf("null
");
}
// 从尾到头打印链表
void displayBackward(DoublyLinkedList* list) {
if (isEmpty(list)) {
printf("链表为空
");
return;
}
printf("null <- ");
Node* current = list->tail;
while (current != NULL) {
printf("%d", current->data);
if (current->prev != NULL) {
printf(" <-> ");
} else {
printf(" -> ");
}
current = current->prev;
}
printf("null
");
}
// 释放链表内存
void freeList(DoublyLinkedList* list) {
Node* current = list->head;
Node* next;
while (current != NULL) {
next = current->next;
free(current);
current = next;
}
free(list);
}
// 使用示例
int main() {
DoublyLinkedList* list = createList();
insertAtTail(list, 10);
insertAtTail(list, 20);
insertAtTail(list, 30);
insertAtHead(list, 5);
printf("从头到尾打印：
");
displayForward(list); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
printf("从尾到头打印：
");
displayBackward(list); // 输出: null <- 30 <-> 20 <-> 10 <-> 5 -> null
insertAtPosition(list, 15, 2);
printf("插入15到位置2后：
");
displayForward(list); // 输出: null <- 5 <-> 10 <-> 15 <-> 20 <-> 30 -> null
deleteNode(list, 15);
printf("删除15后：
");
displayForward(list); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
printf("查找结果: %s
", search(list, 20) ? "true" : "false"); // 输出: 查找结果: true
printf("链表长度: %d
", size(list)); // 输出: 链表长度: 4
deleteHead(list);
printf("删除头节点后：
");
displayForward(list); // 输出: null <- 10 <-> 20 <-> 30 -> null
deleteTail(list);
printf("删除尾节点后：
");
displayForward(list); // 输出: null <- 10 <-> 20 -> null
// 释放内存
freeList(list);
return 0;
}
C++ 实现
▼C++复制代码#include
// 定义节点类
class Node {
public:
int data;
Node* next;
Node* prev;
// 构造函数
Node(int data) {
this->data = data;
this->next = nullptr;
this->prev = nullptr;
}
};
// 双向链表类
class DoublyLinkedList {
private:
Node* head;
Node* tail;
int size;
public:
// 构造函数
DoublyLinkedList() {
head = nullptr;
tail = nullptr;
size = 0;
}
// 析构函数
~DoublyLinkedList() {
Node* current = head;
Node* next = nullptr;
while (current != nullptr) {
next = current->next;
delete current;
current = next;
}
head = nullptr;
tail = nullptr;
}
// 判断链表是否为空
bool isEmpty() {
return head == nullptr;
}
// 获取链表大小
int getSize() {
return size;
}
// 在链表头部插入节点
void insertAtHead(int data) {
Node* newNode = new Node(data);
if (isEmpty()) {
head = newNode;
tail = newNode;
} else {
newNode->next = head;
head->prev = newNode;
head = newNode;
}
size++;
}
// 在链表尾部插入节点
void insertAtTail(int data) {
Node* newNode = new Node(data);
if (isEmpty()) {
head = newNode;
tail = newNode;
} else {
tail->next = newNode;
newNode->prev = tail;
tail = newNode;
}
size++;
}
// 在指定位置插入节点
void insertAtPosition(int data, int position) {
// 位置无效
if (position < 0 || position > size) {
std::cout << "位置无效" << std::endl;
return;
}
// 插入位置为0，相当于在头部插入
if (position == 0) {
insertAtHead(data);
return;
}
// 插入位置为size，相当于在尾部插入
if (position == size) {
insertAtTail(data);
return;
}
// 插入到中间位置
Node* newNode = new Node(data);
// 判断从头部还是尾部遍历更快
if (position <= size / 2) {
// 从头部遍历
Node* current = head;
for (int i = 0; i < position; i++) {
current = current->next;
}
// 在current之前插入新节点
newNode->prev = current->prev;
newNode->next = current;
current->prev->next = newNode;
current->prev = newNode;
} else {
// 从尾部遍历
Node* current = tail;
for (int i = size - 1; i > position; i--) {
current = current->prev;
}
// 在current之前插入新节点
newNode->prev = current->prev;
newNode->next = current;
current->prev->next = newNode;
current->prev = newNode;
}
size++;
}
// 删除头节点
void deleteHead() {
if (isEmpty()) {
std::cout << "链表为空，无法删除" << std::endl;
return;
}
Node* temp = head;
if (head == tail) {
// 只有一个节点
head = nullptr;
tail = nullptr;
} else {
head = head->next;
head->prev = nullptr;
}
delete temp;
size--;
}
// 删除尾节点
void deleteTail() {
if (isEmpty()) {
std::cout << "链表为空，无法删除" << std::endl;
return;
}
Node* temp = tail;
if (head == tail) {
// 只有一个节点
head = nullptr;
tail = nullptr;
} else {
tail = tail->prev;
tail->next = nullptr;
}
delete temp;
size--;
}
// 删除指定位置的节点
void deleteAtPosition(int position) {
// 位置无效
if (position < 0 || position >= size) {
std::cout << "位置无效" << std::endl;
return;
}
// 删除头节点
if (position == 0) {
deleteHead();
return;
}
// 删除尾节点
if (position == size - 1) {
deleteTail();
return;
}
// 删除中间节点
Node* current;
// 判断从头部还是尾部遍历更快
if (position <= size / 2) {
// 从头部遍历
current = head;
for (int i = 0; i < position; i++) {
current = current->next;
}
} else {
// 从尾部遍历
current = tail;
for (int i = size - 1; i > position; i--) {
current = current->prev;
}
}
current->prev->next = current->next;
current->next->prev = current->prev;
delete current;
size--;
}
// 删除第一个值为data的节点
void deleteNode(int data) {
if (isEmpty()) {
std::cout << "链表为空，无法删除" << std::endl;
return;
}
// 删除的是头节点
if (head->data == data) {
deleteHead();
return;
}
// 删除的是尾节点
if (tail->data == data) {
deleteTail();
return;
}
// 删除的是中间节点
Node* current = head->next;
while (current != nullptr && current != tail) {
if (current->data == data) {
current->prev->next = current->next;
current->next->prev = current->prev;
delete current;
size--;
return;
}
current = current->next;
}
std::cout << "未找到要删除的元素" << std::endl;
}
// 查找节点
bool search(int data) {
if (isEmpty()) {
return false;
}
Node* current = head;
while (current != nullptr) {
if (current->data == data) {
return true;
}
current = current->next;
}
return false;
}
// 从头到尾打印链表
void displayForward() {
if (isEmpty()) {
std::cout << "链表为空" << std::endl;
return;
}
std::cout << "null <- ";
Node* current = head;
while (current != nullptr) {
std::cout << current->data;
if (current->next != nullptr) {
std::cout << " <-> ";
} else {
std::cout << " -> ";
}
current = current->next;
}
std::cout << "null" << std::endl;
}
// 从尾到头打印链表
void displayBackward() {
if (isEmpty()) {
std::cout << "链表为空" << std::endl;
return;
}
std::cout << "null <- ";
Node* current = tail;
while (current != nullptr) {
std::cout << current->data;
if (current->prev != nullptr) {
std::cout << " <-> ";
} else {
std::cout << " -> ";
}
current = current->prev;
}
std::cout << "null" << std::endl;
}
};
// 使用示例
int main() {
DoublyLinkedList list;
list.insertAtTail(10);
list.insertAtTail(20);
list.insertAtTail(30);
list.insertAtHead(5);
std::cout << "从头到尾打印：" << std::endl;
list.displayForward(); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
std::cout << "从尾到头打印：" << std::endl;
list.displayBackward(); // 输出: null <- 30 <-> 20 <-> 10 <-> 5 -> null
list.insertAtPosition(15, 2);
std::cout << "插入15到位置2后：" << std::endl;
list.displayForward(); // 输出: null <- 5 <-> 10 <-> 15 <-> 20 <-> 30 -> null
list.deleteNode(15);
std::cout << "删除15后：" << std::endl;
list.displayForward(); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null
std::cout << "查找结果: " << (list.search(20) ? "true" : "false") << std::endl; // 输出: 查找结果: true
std::cout << "链表长度: " << list.getSize() << std::endl; // 输出: 链表长度: 4
list.deleteHead();
std::cout << "删除头节点后：" << std::endl;
list.displayForward(); // 输出: null <- 10 <-> 20 <-> 30 -> null
list.deleteTail();
std::cout << "删除尾节点后：" << std::endl;
list.displayForward(); // 输出: null <- 10 <-> 20 -> null
return 0;
}
优缺点
优点
双向遍历：可以从前向后或从后向前遍历，增加了灵活性
某些操作更快：如果位置靠近尾部，可以从尾部开始遍历，提高效率
实现更多操作：如反向遍历、直接访问前驱节点等单向链表难以实现的操作
缺点
内存开销大：每个节点需要额外存储一个指针，增加了内存消耗
实现复杂：相比单向链表，实现和维护更复杂
操作更慢：插入和删除需要处理更多的指针关系，稍微增加了操作的复杂度
不适合内存受限环境：因为每个节点占用更多内存
应用场景
浏览器历史记录：前进和后退功能
双向迭代器：需要双向遍历的集合数据结构
文本编辑器：光标移动和文本编辑
撤销/重做功能：应用中的操作历史管理
音乐播放器：上一首/下一首歌曲导航
扩展：循环双向链表
循环双向链表是双向链表的变种，尾节点的后向指针指向头节点，头节点的前向指针指向尾节点，形成一个环。这种结构的链表没有明确的开始和结束点，可以从任何节点开始遍历整个链表。
▼Java复制代码// 循环双向链表的实现修改
public void insertAtHead(int data) {
Node newNode = new Node(data);
if (isEmpty()) {
head = newNode;
tail = newNode;
// 形成循环
head.next = head;
head.prev = head;
} else {
newNode.next = head;
newNode.prev = tail;
head.prev = newNode;
tail.next = newNode;
head = newNode;
}
size++;
}
// 其他方法也需要相应调整...
测验
1）如何检测双向链表中是否存在环（循环）？
2）如何在不使用额外空间的情况下翻转一个双向链表？
3）如何合并两个已排序的双向链表，且保证结果仍然有序？
4）如何实现一个双向链表的中间节点查找，要求只遍历一次链表？
测验答案
1）检测双向链表中是否存在环：
▼Java复制代码public boolean hasCycle() {
if (isEmpty() || size <= 1) {
return false;
}
// 在正确的双向链表中，每个节点的next.prev应该等于自己
// 如果存在环，可能会出现不一致
Node current = head;
while (current != null) {
if (current.next != null && current.next.prev != current) {
return true;
}
current = current.next;
// 如果回到了头节点，说明存在循环
if (current == head) {
return true;
}
}
return false;
}
2）翻转双向链表：
▼Java复制代码public void reverse() {
if (isEmpty() || size == 1) {
return;
}
Node current = head;
Node temp = null;
// 交换每个节点的前向和后向指针
while (current != null) {
// 保存下一个节点
temp = current.next;
// 交换当前节点的前向和后向指针
current.next = current.prev;
current.prev = temp;
// 如果前一个节点为null，当前节点将成为新的尾节点
if (current.next == null) {
tail = current;
}
// 移动到下一个节点
current = temp;
// 如果到达原始链表的头部，当前节点将成为新的头节点
if (current == null && temp != null) {
head = temp.prev;
}
}
// 交换头尾节点
Node oldHead = head;
head = tail;
tail = oldHead;
}
3）合并两个有序双向链表：
▼Java复制代码public static DoublyLinkedList mergeSortedLists(DoublyLinkedList list1, DoublyLinkedList list2) {
DoublyLinkedList result = new DoublyLinkedList();
Node current1 = list1.head;
Node current2 = list2.head;
// 比较两个链表的节点，将较小的加入结果链表
while (current1 != null && current2 != null) {
if (current1.data <= current2.data) {
result.insertAtTail(current1.data);
current1 = current1.next;
} else {
result.insertAtTail(current2.data);
current2 = current2.next;
}
}
// 将剩余节点加入结果链表
while (current1 != null) {
result.insertAtTail(current1.data);
current1 = current1.next;
}
while (current2 != null) {
result.insertAtTail(current2.data);
current2 = current2.next;
}
return result;
}
4）查找中间节点：
▼Java复制代码public Node findMiddleNode() {
if (isEmpty()) {
return null;
}
if (head == tail) {
return head;
}
// 使用快慢指针
Node slow = head;
Node fast = head;
// 快指针每次走两步，慢指针每次走一步
// 当快指针到达尾部时，慢指针就在中间
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
相关LeetCode热门题目
本节的推荐题目：
146. LRU 缓存 - 使用双向链表实现LRU缓存
430. 扁平化多级双向链表 - 将多级双向链表扁平化
138. 复制带随机指针的链表 - 深拷贝一个复杂链表
61. 旋转链表 - 将链表向右旋转k个位置
1472. 设计浏览器历史记录 - 使用双向链表实现浏览器历史功能