双向链表是一种线性数据结构,其中每个节点包含数据和指向前一个与后一个节点的指针。支持双向遍历,适用于需要双向操作的场景。
双向链表是链表的一种变体,其中每个节点包含三个部分:数据域、前向指针和后向指针。前向指针指向前一个节点,后向指针指向后一个节点。这种结构使得链表可以从两个方向进行遍历,增加了灵活性。

与单向链表相比,双向链表支持双向遍历,并且在某些操作上更高效,例如删除给定节点或在特定节点前插入新节点。双向链表的头结点的前向指针和尾节点的后向指针通常指向null,表示链表的边界。
▼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复制代码// 定义节点类 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复制代码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复制代码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\n", list.Search(20)) // 输出: 查找结果: true fmt.Printf("链表长度: %d\n", 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复制代码#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 定义节点结构 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("内存分配失败\n"); 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("内存分配失败\n"); 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("位置无效\n"); 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("链表为空,无法删除\n"); 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("链表为空,无法删除\n"); 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("位置无效\n"); 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("链表为空,无法删除\n"); 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("未找到要删除的元素\n"); } // 查找节点 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("链表为空\n"); 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\n"); } // 从尾到头打印链表 void displayBackward(DoublyLinkedList* list) { if (isEmpty(list)) { printf("链表为空\n"); 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\n"); } // 释放链表内存 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("从头到尾打印:\n"); displayForward(list); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null printf("从尾到头打印:\n"); displayBackward(list); // 输出: null <- 30 <-> 20 <-> 10 <-> 5 -> null insertAtPosition(list, 15, 2); printf("插入15到位置2后:\n"); displayForward(list); // 输出: null <- 5 <-> 10 <-> 15 <-> 20 <-> 30 -> null deleteNode(list, 15); printf("删除15后:\n"); displayForward(list); // 输出: null <- 5 <-> 10 <-> 20 <-> 30 -> null printf("查找结果: %s\n", search(list, 20) ? "true" : "false"); // 输出: 查找结果: true printf("链表长度: %d\n", size(list)); // 输出: 链表长度: 4 deleteHead(list); printf("删除头节点后:\n"); displayForward(list); // 输出: null <- 10 <-> 20 <-> 30 -> null deleteTail(list); printf("删除尾节点后:\n"); displayForward(list); // 输出: null <- 10 <-> 20 -> null // 释放内存 freeList(list); return 0; }
▼C++复制代码#include <iostream> // 定义节点类 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; // 移动到下一个节点 current = temp; } // 交换头尾节点:原来的尾节点成为新的头节点,原来的头节点成为新的尾节点 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; }
本节的推荐题目: