golang实现链表(golang实现链表反转)

介绍

链表是一种基本的数据结构，它由多个节点组成，每个节点包含数据和指向下一个节点的指针。常见的链表有单向链表、双向链表和循环链表等。在golang中，也可以很方便地实现链表。

实现单向链表

在golang中，我们可以用struct来定义链表节点，每个节点包含一个value和一个next指针。value用来存储数据，next指针用来指向下一个节点。

```go
type ListNode struct {
Val int
Next *ListNode
}
```

可以看出，这是一个单向链表节点的定义，它的值是整数类型，它的指针是下一个节点的指针。接着，我们可以定义链表的根节点：

```go
type List struct {
Head *ListNode
}
```

链表的结构就由链表的根节点来维护，整个链表的信息就保存在Head指针中。要实现一个单向链表的基本操作，包括：

• 插入节点
• 删除节点
• 查找节点
• 遍历链表等

以下是一些链表操作的示例代码：

```go
//头节点插入
func (list *List) InsertAtHead(val int) {
newNode := &ListNode{Val: val, Next: list.Head}
list.Head = newNode
}

//尾部插入
func (list *List) InsertAtTail(val int) {
newNode := &ListNode{Val: val, Next: nil}

if list.Head == nil {
list.Head = newNode
} else {
cur := list.Head
for cur.Next != nil {
cur = cur.Next
}
cur.Next = newNode
}
}

//查找节点
func (list *List) Find(val int) *ListNode {
cur := list.Head
for cur != nil {
if cur.Val == val {
return cur
}
cur = cur.Next
}
return nil
}

//删除节点
func (list *List) Delete(val int) {
if list.Head == nil {
return
}

if list.Head.Val == val {
list.Head = list.Head.Next
return
}

cur := list.Head
for cur.Next != nil {
if cur.Next.Val == val {
cur.Next = cur.Next.Next
return
}
cur = cur.Next
}
}
```

实现双向链表

与单向链表相比，双向链表节点多了一个指向上一个节点的指针。即每个节点包含value、next和prev三个部分。

```go
type ListNode struct {
Val int
Next *ListNode
Prev *ListNode
}
```

同样地，我们也可以用List来维护整个双向链表，由于双向链表拥有指向前一个节点的指针，因此我们可以像单向链表那样实现增删查等基本操作。不过，由于双向链表具有正反向遍历的特点，因此我们可以通过指向Head和Tail节点的指针去实现对整个双向链表的遍历。

```go
type List struct {
Head *ListNode
Tail *ListNode
}
```

以下是一些双向链表操作的示例代码：

```go
//头节点插入
func (list *List) InsertAtHead(val int) {
newNode := &ListNode{Val: val, Next: list.Head}

if list.Head != nil {
list.Head.Prev = newNode
} else {
list.Tail = newNode
}
list.Head = newNode
}

//尾部插入
func (list *List) InsertAtTail(val int) {
newNode := &ListNode{Val: val, Next: nil, Prev: list.Tail}

if list.Head == nil {
list.Head = newNode
} else {
list.Tail.Next = newNode
}
list.Tail = newNode
}

//查找节点
func (list *List) Find(val int) *ListNode {
cur := list.Head
for cur != nil {
if cur.Val == val {
return cur
}
cur = cur.Next
}
return nil
}

//删除节点
func (list *List) Delete(val int) {
if list.Head == nil {
return
}

cur := list.Head
for cur != nil {
if cur.Val == val {
if cur.Prev != nil {
cur.Prev.Next = cur.Next
} else {
list.Head = cur.Next
}

if cur.Next != nil {
cur.Next.Prev = cur.Prev
} else {
list.Tail = cur.Prev
}

return
}
cur = cur.Next
}
}
```

总结

在golang中，实现链表是一件相对简单的事情。无论是单向链表，还是双向链表，我们只需要使用struct定义链表节点，然后用List维护整个链表即可实现常用的基本操作。需要注意的是，在实现双向链表的时候，我们需要在每个节点里面保存一个prev指针，用于指向上一个节点，这样就可以实现正反双向遍历了。需要注意的是，指针的操作要特别小心，否则很容易出现空指针或者指针错乱的问题。