数据结构-链表#

链表的定义#

链表（linked list）是一种线性数据结构，其中的每个元素都是一个节点对象，各个节点通过引用相连接。引用记录了下一个节点的内存地址，通过它可以从当前节点访问到下一个节点。链表的设计使得各个节点可以分散存储在内存各处，它们的内存地址无须连续。

链表的分类#

单向链表：即本文重点介绍的普通链表。单向链表的节点包含值和指向下一节点的引用两项数据。首个节点称为头节点，将最后一个节点称为尾节点，尾节点指向空 nil 。
环形链表：令单向链表的尾节点指向头节点（首尾相接），则得到一个环形链表。在环形链表中，任意节点都可以视作头节点。
双向链表：与单向链表相比，双向链表记录了两个方向的引用。双向链表的节点定义同时包含指向后继节点（下一个节点）和前驱节点（上一个节点）的引用（指针）。相较于单向链表，双向链表更具灵活性，可以朝两个方向遍历链表，但相应地也需要占用更多的内存空间。

链表的结构定义#

1
// ListNode 链表节点结构体
2
type ListNode struct {
3
  Val  int       // 节点的值
4
  Next *ListNode // 指向下一个节点的指针
5
}

初始化一个链表节点#

1
// NewListNode 创建一个新节点
2
// Params:
3
//   - val: 节点值
4
// Return:
5
//   - node: 链表节点
6
func NewListNode(val int) *ListNode {
7
  return &ListNode{Val: val, Next: nil}
8
}

初始化一个链表#

1
// NewLinkedList 创建一个新链表
2
// Params:
3
//   - size: 链表长度
4
// Return:
5
//   - headNode: 链表头节点
6
func NewLinkedList(size int) (headNode *ListNode) {
7
  headNode = nil // 头节点指针
8
  var currentNode *ListNode = nil // 当前节点指针
9
  // 前往后创建节点
10
  for i := 0; i < size; i++ {
11
    newNode := NewListNode(i) //  创建新节点
12
    if headNode == nil {
13
      headNode = newNode // 头节点为空则将头节点指向新节点
14
    }
15
    if currentNode == nil {
16
      currentNode = newNode //  当前节点为空则将当前节点指向新节点
17
    }
18
    currentNode.Next = newNode //  当前节点指向新节点
19
    currentNode = newNode //
20
  }
21
  return headNode
22
}

链表的常用操作#

打印(遍历)链表#

1
// Print 打印链表
2
func (l *ListNode) Print() {
3
  for l != nil {
4
    fmt.Print(l.Val, " ")
5
    l = l.Next // 指针后移
6
  }
7
  fmt.Println()
8
}

插入新节点#

1
// InsertNode 在头节点后插入新节点
2
// Params:
3
//   - headNode: 链表头节点
4
//   - newNode: 新节点
5
func InsertNode(headNode *ListNode, newNode *ListNode) {
6
  newNode.Next = headNode.Next // 新节点的Next指向头节点的Next
7
  headNode.Next = newNode      // 头节点的Next指向新节点
8
}

删除节点#

1
// DeleteNode 删除头节点后的节点
2
// Params:
3
//   - headNode: 链表头节点
4
func DeleteNode(headNode *ListNode) {
5
  headNode.Next = headNode.Next.Next // 头节点的Next指向头节点的Next的Next
6
}

获取链表的第index个节点#

1
// GetNode 获取链表中的第index个节点
2
// Params:
3
//   - headNode: 链表头节点
4
//   - index: 节点索引
5
//
6
// Return:
7
//   - node: 节点
8
func GetNode(headNode *ListNode, index int) (node *ListNode) {
9
  currentNode := headNode
10
  for i := 0; i <= index; i++ {
11
    if i == index {
12
      return currentNode
13
    }
14
    currentNode = currentNode.Next
15
  }
16
  return nil
17
}

获取链表中第一个值为val的节点#

1
// FindNode 获取链表中第一个值为val的节点
2
// Params:
3
//   - headNode: 链表头节点
4
//   - val: 节点值
5
//
6
// Return:
7
//   - node: 节点
8
func FindNode(headNode *ListNode, val int) (node *ListNode) {
9
  currentNode := headNode
10
  for currentNode != nil {
11
    if currentNode.Val == val {
12
      return currentNode
13
    }
14
    currentNode = currentNode.Next
15
  }
16
  return nil
17
}

主函数示例代码#

1
func main() {
2
  linkedList := NewLinkedList(5)
3
  linkedList.Print()
4

5
  newNode := NewListNode(100)
6
  InsertNode(linkedList, newNode)
7
  fmt.Println("After insert a new node")
8
  linkedList.Print()
9

10
  DeleteNode(linkedList)
11
  fmt.Println("After delete a node")
12
  linkedList.Print()
13

14
  fmt.Println("Get node 2: ", GetNode(linkedList, 2).Val)
15
  fmt.Println("Find node value==4: ", FindNode(linkedList, 4).Val)
16
}

运行结果:

双向链表示例#

1
/* 双向链表节点结构体 */
2
type DoublyListNode struct {
3
    Val  int             // 节点值
4
    Next *DoublyListNode // 指向后继节点的指针
5
    Prev *DoublyListNode // 指向前驱节点的指针
6
}
7

8
// NewDoublyListNode 初始化
9
func NewDoublyListNode(val int) *DoublyListNode {
10
    return &DoublyListNode{
11
        Val:  val,
12
        Next: nil,
13
        Prev: nil,
14
    }
15
}

其他操作大差不差，这里不再赘述。

数据结构-树

数据结构-栈