Golang 链表详解

﹏ヽ暗。殇╰゛Y 2024-02-23 01:14 89阅读 0赞

#### 阅读目录 ####

*  链表包
 *  Golang 链表
 *   *  1 单向链表添加
     *  2 双向链表（Doubly Linked List）：
     *  3 循环链表（Circular Linked List）：
 *  Go 合并两个有序链表

## 链表包 ##

[Go语言的list包（列表）链表][Go_list]

## Golang 链表 ##

链表（LinkedList）是一种基本的线性数据结构，用于存储一系列元素，其中每个元素被包装在一个节点（Node）中。每个节点通常包括两个部分：一个存储数据元素的字段和一个指向下一个节点的引用（指针或引用）字段。这种结构允许在内存中动态分配和管理元素，并且支持插入和删除操作，而无需预先分配固定大小的内存块。

链表与数组不同，数组要求所有元素在内存中是相邻的，并且具有固定的大小。链表允许元素在内存中分散存储，每个元素只知道下一个元素的位置。这使得链表更灵活，尤其在需要频繁插入和删除元素的情况下。

有几种常见类型的链表，包括：

1.  **单向链表（Singly Linked List）**：每个节点只包含一个指向下一个节点的指针。它是最简单的链表类型。
2.  **双向链表（Doubly Linked List）**：每个节点包含一个指向下一个节点和一个指向前一个节点的指针。这使得在双向链表中可以更容易地进行前向和后向遍历。
3.  **循环链表（Circular Linked List）**：最后一个节点指向第一个节点，形成一个循环。这可以用于某些特定场景，如循环队列。

链表的一些常见操作包括插入节点、删除节点、搜索特定元素、遍历整个链表等。链表在计算机科学中应用广泛，用于实现许多数据结构，如栈、队列、哈希表的底层存储，以及在算法中进行许多操作。链表的主要优点是其动态性，但缺点是它通常需要更多的内存开销来存储指针信息，并且在访问元素时需要顺序遍历，而不像数组那样可以直接访问索引位置。

### 1 单向链表添加 ###

单向链表（Singly Linked List）：  
每个节点只包含一个指向下一个节点的指针。  
它是最简单的链表类型。

package main
    
    import "fmt"
    
    // 定义链表节点
    type Node struct {
        
    	Data int
    	Next *Node
    }
    
    // 定义链表结构
    type LinkedList struct {
        
    	Head *Node
    }
    
    // 向链表末尾添加新节点
    func (list *LinkedList) Append(data int) {
        
    	newNode := &Node{
        Data: data, Next: nil}
    
    	if list.Head == nil {
        
    		list.Head = newNode
    	} else {
        
    		current := list.Head
    		for current.Next != nil {
        
    			current = current.Next
    		}
    		current.Next = newNode
    	}
    }
    
    // 遍历并打印链表
    func (list *LinkedList) Display() {
        
    	current := list.Head
    	for current != nil {
        
    		fmt.Printf("%d -> ", current.Data)
    		current = current.Next
    	}
    	fmt.Println("nil")
    }
    
    func main() {
        
    	myList := LinkedList{
        }
    	myList.Append(1)
    	myList.Append(2)
    	myList.Append(3)
    
    	myList.Display() // 输出: 1 -> 2 -> 3 -> nil
    }

### 2 双向链表（Doubly Linked List）： ###

每个节点包含一个指向下一个节点和一个指向前一个节点的指针。  
这使得在双向链表中可以更容易地进行前向和后向遍历。

package main
    
    import "fmt"
    
    // Node 表示双向链表的节点
    type Node struct {
        
    	Data int
    	Prev *Node
    	Next *Node
    }
    
    // DoublyLinkedList 表示双向链表
    type DoublyLinkedList struct {
        
    	Head *Node
    	Tail *Node
    }
    
    // NewDoublyLinkedList 创建一个新的双向链表
    func NewDoublyLinkedList() *DoublyLinkedList {
        
    	return &DoublyLinkedList{
        }
    }
    
    // Append 在双向链表的末尾添加一个新节点
    func (dll *DoublyLinkedList) Append(data int) {
        
    	newNode := &Node{
        Data: data}
    
    	if dll.Head == nil {
        
    		dll.Head = newNode
    		dll.Tail = newNode
    	} else {
        
    		newNode.Prev = dll.Tail
    		dll.Tail.Next = newNode
    		dll.Tail = newNode
    	}
    }
    
    // ForwardTraverse 前向遍历双向链表
    func (dll *DoublyLinkedList) ForwardTraverse() {
        
    	current := dll.Head
    	for current != nil {
        
    		fmt.Printf("%d -> ", current.Data)
    		current = current.Next
    	}
    	fmt.Println("nil")
    }
    
    // ReverseTraverse 后向遍历双向链表
    func (dll *DoublyLinkedList) ReverseTraverse() {
        
    	current := dll.Tail
    	for current != nil {
        
    		fmt.Printf("%d -> ", current.Data)
    		current = current.Prev
    	}
    	fmt.Println("nil")
    }
    
    func main() {
        
    	dll := NewDoublyLinkedList()
    
    	dll.Append(1)
    	dll.Append(2)
    	dll.Append(3)
    
    	fmt.Println("Forward Traverse:")
    	dll.ForwardTraverse()
    
    	fmt.Println("Reverse Traverse:")
    	dll.ReverseTraverse()
    }

### 3 循环链表（Circular Linked List）： ###

最后一个节点指向第一个节点，形成一个循环。  
这可以用于某些特定场景，如循环队列。

package main
    
    import "fmt"
    
    // Node 表示循环链表的节点
    type Node struct {
        
    	Data int
    	Next *Node
    }
    
    // CircularLinkedList 表示循环链表
    type CircularLinkedList struct {
        
    	Head *Node
    	Tail *Node
    }
    
    // NewCircularLinkedList 创建一个新的循环链表
    func NewCircularLinkedList() *CircularLinkedList {
        
    	return &CircularLinkedList{
        }
    }
    
    // Append 在循环链表的末尾添加一个新节点
    func (cll *CircularLinkedList) Append(data int) {
        
    	newNode := &Node{
        Data: data}
    	if cll.Head == nil {
        
    		cll.Head = newNode
    		newNode.Next = newNode // 使链表循环
    		cll.Tail = newNode
    	} else {
        
    		newNode.Next = cll.Head
    		cll.Tail.Next = newNode
    		cll.Tail = newNode
    	}
    }
    
    // Display 打印循环链表的内容
    func (cll *CircularLinkedList) Display() {
        
    	if cll.Head == nil {
        
    		fmt.Println("Empty Circular Linked List")
    		return
    	}
    
    	current := cll.Head
    	for {
        
    		fmt.Printf("%d -> ", current.Data)
    		current = current.Next
    		if current == cll.Head {
        
    			break
    		}
    	}
    	fmt.Println()
    }
    
    func main() {
        
    	cll := NewCircularLinkedList()
    
    	cll.Append(1)
    	cll.Append(2)
    	cll.Append(3)
    
    	fmt.Println("Circular Linked List:")
    	cll.Display()
    }

## Go 合并两个有序链表 ##

在 Go 语言中合并两个有序链表，你可以逐个比较节点的值，然后按顺序将它们连接起来。以下是一个示例代码，演示如何合并两个有序链表：

package main
    
    import "fmt"
    
    // ListNode 表示链表节点
    type ListNode struct {
        
    	Val  int
    	Next *ListNode
    }
    
    // MergeTwoLists 合并两个有序链表
    func MergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
        
    	// 创建一个虚拟头节点，用于简化合并操作
    	dummy := &ListNode{
        }
    	current := dummy
    
    	// 比较 l1 和 l2 的节点值，按顺序合并
    	for l1 != nil && l2 != nil {
        
    		if l1.Val < l2.Val {
        
    			current.Next = l1
    			l1 = l1.Next
    		} else {
        
    			current.Next = l2
    			l2 = l2.Next
    		}
    		current = current.Next
    	}
    
    	// 处理剩余的节点
    	if l1 != nil {
        
    		current.Next = l1
    	}
    	if l2 != nil {
        
    		current.Next = l2
    	}
    
    	return dummy.Next
    }
    
    // PrintList 打印链表
    func PrintList(head *ListNode) {
        
    	current := head
    	for current != nil {
        
    		fmt.Printf("%d -> ", current.Val)
    		current = current.Next
    	}
    	fmt.Println("nil")
    }
    
    func main() {
        
    	// 创建两个有序链表
    	l1 := &ListNode{
        Val: 1, Next: &ListNode{
        Val: 2, Next: &ListNode{
        Val: 4, Next: nil}}}
    	l2 := &ListNode{
        Val: 1, Next: &ListNode{
        Val: 3, Next: &ListNode{
        Val: 5, Next: nil}}}
    
    	fmt.Println("List 1:")
    	PrintList(l1)
    
    	fmt.Println("List 2:")
    	PrintList(l2)
    
    	// 合并两个链表
    	merged := MergeTwoLists(l1, l2)
    
    	fmt.Println("Merged List:")
    	PrintList(merged)
    }

这个示例中，我们定义了一个 `ListNode` 结构来表示链表节点，然后编写了 `MergeTwoLists` 函数来合并两个有序链表。创建了一个虚拟头节点 `dummy`，然后逐个比较 `l1` 和 `l2` 的节点值，按顺序合并它们。最后，我们通过 `PrintList` 函数打印合并后的链表。

在示例中，我们创建了两个有序链表 `l1` 和 `l2`，并将它们合并为 `merged` 链表。

[Go_list]: https://wgchen.blog.csdn.net/article/details/129212481