# 链表以及golang介入式链表的实现

sheepbao.github.io · · 590 次点击 · · 开始浏览

## go标准库的双向链表

golang的标准库中实现了一个双向链表，该链表可以存储任何数据，先看看使用标准库链表的例子：

``````package list_test

import (
"container/list"
"fmt"
"testing"
)

func TestList(t *testing.T) {
// Create a new list and put some numbers in it.
l := list.New()
e4 := l.PushBack(4)
e1 := l.PushFront(1)
l.InsertBefore(3, e4)
l.InsertAfter(2, e1)

// Iterate through list and print its contents.
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
// output
// 1
// 2
// 3
// 4
``````

### 实现该链表的数据结构

``````// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len  int     // current list length excluding (this) sentinel element
}

// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element

// The list to which this element belongs.
list *List

// The value stored with this element.
Value interface{}
}
``````

## 介入式链表(intrusive list)

### 实现代码

``````package list

type Intrusive interface {
Next() Intrusive
Prev() Intrusive
}

// List provides the implementation of intrusive linked lists
type List struct {
prev Intrusive
next Intrusive
}

func (l *List) Next() Intrusive {
return l.next
}

func (l *List) Prev() Intrusive {
return l.prev
}

func (l *List) AddNext(i Intrusive) {
l.next = i
}

func (l *List) AddPrev(i Intrusive) {
l.prev = i
}

func (l *List) Reset() {
l.prev = nil
l.next = nil
}

func (l *List) Empty() bool {
return l.prev == nil
}

// Front returns the first element of list l or nil.
func (l *List) Front() Intrusive {
return l.prev
}

// Back returns the last element of list l or nil.
func (l *List) Back() Intrusive {
return l.next
}

// PushFront inserts the element e at the front of list l.
func (l *List) PushFront(e Intrusive) {

if l.prev != nil {
} else {
l.next = e
}
l.prev = e
}

// PushBack inserts the element e at the back of list l.
func (l *List) PushBack(e Intrusive) {

if l.next != nil {
} else {
l.prev = e
}
l.next = e
}

// InsertAfter inserts e after b.
func (l *List) InsertAfter(e, b Intrusive) {
a := b.Next()

if a != nil {
} else {
l.next = e
}
}

// InsertBefore inserts e before a.
func (l *List) InsertBefore(e, a Intrusive) {
b := a.Prev()

if b != nil {
} else {
l.prev = e
}
}

// Remove removes e from l.
func (l *List) Remove(e Intrusive) {
prev := e.Prev()
next := e.Next()

if prev != nil {
} else {
l.prev = next
}

if next != nil {
} else {
l.next = prev
}
}
``````

``````package list

import (
"fmt"
"testing"
)

func TestIntrusiveList(t *testing.T) {
type E struct {
List
data int
}
// Create a new list and put some numbers in it.
l := List{}
e4 := &E{data: 4}
e1 := &E{data: 1}
l.PushBack(e4)
l.PushFront(e1)
l.InsertBefore(&E{data: 3}, e4)
l.InsertAfter(&E{data: 2}, e1)

for e := l.Front(); e != nil; e = e.Next() {
fmt.Printf("e: %+v\n", e)
fmt.Printf("data: %d\n", e.(*E).data)
}
}

// output
// e: &{List:{prev:<nil> next:0xc4200789c0} data:1}
// data: 1
// e: &{List:{prev:0xc420078960 next:0xc420078990} data:2}
// data: 2
// e: &{List:{prev:0xc4200789c0 next:0xc420078930} data:3}
// data: 3
// e: &{List:{prev:0xc420078990 next:<nil>} data:4}
// data: 4

``````

`E`里嵌入`List`即可作为链表的节点，是不是很方便，其实当我写完介入式链表的栗子后，发现其实标准库的链表更方便，哈哈。。因为golang有`interface{}`

## 参考

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

## go标准库的双向链表

golang的标准库中实现了一个双向链表，该链表可以存储任何数据，先看看使用标准库链表的例子：

``````package list_test

import (
"container/list"
"fmt"
"testing"
)

func TestList(t *testing.T) {
// Create a new list and put some numbers in it.
l := list.New()
e4 := l.PushBack(4)
e1 := l.PushFront(1)
l.InsertBefore(3, e4)
l.InsertAfter(2, e1)

// Iterate through list and print its contents.
for e := l.Front(); e != nil; e = e.Next() {
fmt.Println(e.Value)
}
}
// output
// 1
// 2
// 3
// 4
``````

### 实现该链表的数据结构

``````// List represents a doubly linked list.
// The zero value for List is an empty list ready to use.
type List struct {
root Element // sentinel list element, only &root, root.prev, and root.next are used
len  int     // current list length excluding (this) sentinel element
}

// Element is an element of a linked list.
type Element struct {
// Next and previous pointers in the doubly-linked list of elements.
// To simplify the implementation, internally a list l is implemented
// as a ring, such that &l.root is both the next element of the last
// list element (l.Back()) and the previous element of the first list
// element (l.Front()).
next, prev *Element

// The list to which this element belongs.
list *List

// The value stored with this element.
Value interface{}
}
``````

## 介入式链表(intrusive list)

### 实现代码

``````package list

type Intrusive interface {
Next() Intrusive
Prev() Intrusive
}

// List provides the implementation of intrusive linked lists
type List struct {
prev Intrusive
next Intrusive
}

func (l *List) Next() Intrusive {
return l.next
}

func (l *List) Prev() Intrusive {
return l.prev
}

func (l *List) AddNext(i Intrusive) {
l.next = i
}

func (l *List) AddPrev(i Intrusive) {
l.prev = i
}

func (l *List) Reset() {
l.prev = nil
l.next = nil
}

func (l *List) Empty() bool {
return l.prev == nil
}

// Front returns the first element of list l or nil.
func (l *List) Front() Intrusive {
return l.prev
}

// Back returns the last element of list l or nil.
func (l *List) Back() Intrusive {
return l.next
}

// PushFront inserts the element e at the front of list l.
func (l *List) PushFront(e Intrusive) {

if l.prev != nil {
} else {
l.next = e
}
l.prev = e
}

// PushBack inserts the element e at the back of list l.
func (l *List) PushBack(e Intrusive) {

if l.next != nil {
} else {
l.prev = e
}
l.next = e
}

// InsertAfter inserts e after b.
func (l *List) InsertAfter(e, b Intrusive) {
a := b.Next()

if a != nil {
} else {
l.next = e
}
}

// InsertBefore inserts e before a.
func (l *List) InsertBefore(e, a Intrusive) {
b := a.Prev()

if b != nil {
} else {
l.prev = e
}
}

// Remove removes e from l.
func (l *List) Remove(e Intrusive) {
prev := e.Prev()
next := e.Next()

if prev != nil {
} else {
l.prev = next
}

if next != nil {
} else {
l.next = prev
}
}
``````

``````package list

import (
"fmt"
"testing"
)

func TestIntrusiveList(t *testing.T) {
type E struct {
List
data int
}
// Create a new list and put some numbers in it.
l := List{}
e4 := &E{data: 4}
e1 := &E{data: 1}
l.PushBack(e4)
l.PushFront(e1)
l.InsertBefore(&E{data: 3}, e4)
l.InsertAfter(&E{data: 2}, e1)

for e := l.Front(); e != nil; e = e.Next() {
fmt.Printf("e: %+v\n", e)
fmt.Printf("data: %d\n", e.(*E).data)
}
}

// output
// e: &{List:{prev:<nil> next:0xc4200789c0} data:1}
// data: 1
// e: &{List:{prev:0xc420078960 next:0xc420078990} data:2}
// data: 2
// e: &{List:{prev:0xc4200789c0 next:0xc420078930} data:3}
// data: 3
// e: &{List:{prev:0xc420078990 next:<nil>} data:4}
// data: 4

``````

`E`里嵌入`List`即可作为链表的节点，是不是很方便，其实当我写完介入式链表的栗子后，发现其实标准库的链表更方便，哈哈。。因为golang有`interface{}`