Single Linked List

单链表定义

此处将 NodeList 分开定义,方便理解,官方的方法是把两个结构合并,
戳:https://golang.org/src/container/list/list.go?s=2063:2093#L14

type Node struct {
	value interface{}
	next  *Node
}

type List struct {
	len  int
	head *Node
	tail *Node
}

接口列表

非必要可以省略此步骤,此处使用 Interface 只是为了方便阅读和展示。

type SingleLinkedList interface {
	Init()
	Len() int
	PushFront(v interface{})
	PushBack(v interface{})
	Insert(v interface{}, index int) error
	RemoveFront() interface{}
	RemoveBack() interface{}
	Remove(index int) interface{}
	GetHead() *Node
	Get(index int) interface{}
}

初始化

初始化操作,需要手动初始化,也可以实现在首次插入时进行初始化操作。

func (l *List) Init() {
	l.len = 0
	l.head = nil
	l.tail = nil
}

链表长度

func (l *List) Len() int {
	return l.len
}

添加操作

新节点三种插入方式,分别是 头部插入、末尾插入、指定位置插入。

// 从链表头部插入一个新节点
func (l *List) PushFront(v interface{}) {
	node := &Node{
		value: v,
		next:  nil,
	}
	if l.len == 0 {
		l.tail = node
	} else {
		node.next = l.head
	}
	l.head = node
	l.len++
}

// 从链表尾部插入一个新节点
func (l *List) PushBack(v interface{}) {
	node := &Node{
		value: v,
		next:  nil,
	}
	if l.len == 0 {
		l.head = node
	} else {
		l.tail.next = node
	}
	l.tail = node
	l.len++
}

// 指定位置,插入新节点
func (l *List) Insert(v interface{}, index int) error {
	if index >= l.len {
		return errors.New("index error")
	}
	if index == 0 {
		l.PushFront(v)
		return nil
	}
	node := &Node{
		value: v,
		next:  nil,
	}
	prev := l.head
	for i := 1; i < l.len; i++ {
		if i == index {
			node.next = prev.next
			prev.next = node
			l.len++
			return nil
		}
		prev = prev.next
	}

	return errors.New("insert error")
}

移除操作

三种移除操作,移除头部、移除尾部、指定位置移除。

// 移除头部节点
func (l *List) RemoveFront() interface{} {
	if l.len == 0 {
		return nil
	}
	node := l.head
	l.head = l.head.next
	l.len--
	return node.value
}

// 移除尾部节点
func (l *List) RemoveBack() interface{} {
	if l.len == 0 {
		return nil
	}
	node := l.head
	for i := 1; i < l.len-1; i++ {
		node = node.next
	}
	tmp := node.next
	node.next = nil
	l.tail = node
	l.len--
	return tmp.value
}

// 指定位置移除节点
func (l *List) Remove(index int) interface{} {
	if l.len == 0 {
		return nil
	}
	if index == 0 {
		return l.RemoveFront()
	} else if index == l.len-1 {
		return l.RemoveBack()
	}
	node := l.head
	for i := 1; i < index; i++ {
		node = node.next
	}
	tmp := node.next
	node.next = node.next.next
	l.len--
	return tmp.value
}

获取节点

// 获取头部节点
func (l *List) GetHead() *Node {
	return l.head
}

// 获取指定位置的节点值
func (l *List) Get(index int) interface{} {
	if index >= l.len {
		return nil
	}
	node := l.head
	for i := 0; i < l.len; i++ {
		if i == index {
			return node.value
		}
		node = node.next
	}
	return nil
}

测试

测试用例:

func main() {
	var sl SingleLinkedList = &List{}
	sl.Init()
	sl.PushFront(6)
	sl.PushFront(7)
	sl.PushFront(8)
	sl.PushBack(1)
	sl.PushBack(2)
	sl.PushBack(3)
	fmt.Println("r", sl.RemoveFront())
	_ = sl.Insert(9, 0)
	_ = sl.Insert(8, 5)
	fmt.Println("r", sl.RemoveBack())
	fmt.Println("r", sl.RemoveBack())
	fmt.Println("rm", sl.Remove(1))
	fmt.Println("rm", sl.Remove(2))

	fmt.Println("len", sl.Len())
	node := sl.GetHead()
	for {
		fmt.Println(">>>", node.value)
		if node.next == nil {
			break
		}
		node = node.next
	}
	fmt.Println(sl.Get(1))
}

Double Linked List

在 Single Linked List 的基础上修改。

定义

增加了 prev 字段。

type Node struct {
	value interface{}
	next  *Node
	prev  *Node // add prev
}

接口列表

增加了 GetTail 接口,获取尾部节点。

type DoubleLinkedList interface {
	Init()
	Len() int
	PushFront(v interface{})
	PushBack(v interface{})
	Insert(v interface{}, index int) error
	RemoveFront() interface{}
	RemoveBack() interface{}
	Remove(index int) interface{}
	GetHead() *Node
	GetTail() *Node // add
	Get(index int) interface{}
}

插入操作

func (l *List) PushFront(v interface{}) {
	node := &Node{
		value: v,
		next:  nil,
		prev:  nil, // add
	}
	if l.len == 0 {
		l.tail = node
	} else {
		l.head.prev = node // add
		node.next = l.head
	}
	l.head = node
	l.len++
}

func (l *List) PushBack(v interface{}) {
	node := &Node{
		value: v,
		next:  nil,
		prev:  nil, // add
	}
	if l.len == 0 {
		l.head = node
	} else {
		node.prev = l.tail // add
		l.tail.next = node
	}
	l.tail = node
	l.len++
}

指定位置插入节点

这里做了一个判断,以链表长度中值为基准,当插入当位置靠近起点时,从头部开始往中间遍历插入,反之,从末尾往中间遍历插入。

func (l *List) Insert(v interface{}, index int) error {
	// new
	if index >= l.len {
		return errors.New("index error")
	}
	if index == 0 {
		l.PushFront(v)
		return nil
	}
	if index == l.len-1 {
		l.PushBack(v)
		return nil
	}

	mid := l.len / 2 // chose to start from the front or behind

	newNode := &Node{
		value: v,
		next:  nil,
		prev:  nil,
	}
	node := &Node{}
	if index <= mid { // from front
		node = l.head
		for i := 1; i <= mid; i++ {
			if i == index {
				break
			}
			node = node.next
		}
	} else { // from behind
		node = l.tail
		for i := l.len; i > mid; i-- {
			if i == index {
				break
			}
			node = node.prev
		}
	}
	newNode.prev = node
	newNode.next = node.next
	node.next.prev = newNode
	node.next = newNode
	l.len++
	return nil
}

移除操作

移除头部节点、移除尾部节点。

func (l *List) RemoveFront() interface{} {
	if l.len == 0 {
		return nil
	}
	node := l.head
	l.head = l.head.next
	l.head.prev = nil // add
	l.len--
	return node.value
}

func (l *List) RemoveBack() interface{} {
	// new
	if l.len == 0 {
		return nil
	}
	node := l.tail
	l.tail = l.tail.prev
	l.tail.next = nil
	l.len--
	return node.value
}

指定位置移除

移除指定位置的节点,和指定位置插入一样,根据是否更靠近链表两端,从头或尾部开始往反方向遍历。

func (l *List) Remove(index int) interface{} {
	// new
	if l.len == 0 {
		return nil
	}
	if index == 0 {
		return l.RemoveFront()
	} else if index == l.len-1 {
		return l.RemoveBack()
	}

	mid := l.len / 2

	node := &Node{}
	if index <= mid {
		node = l.head
		for i := 1; i <= mid; i++ {
			if i == index {
				break
			}
			node = node.next
		}

	} else {
		node = l.tail
		for i := l.len; i > mid; i-- {
			if i == index {
				break
			}
			node = node.prev
		}
	}
	tmp := node.next
	node.next = tmp.next
	tmp.next.prev = node
	l.len--
	return tmp.value
}

获取节点

// 获取尾部节点,可用于从尾部往前遍历
// add
func (l *List) GetTail() *Node {
	return l.tail
}

// 获取指定节点值
func (l *List) Get(index int) interface{} {
	// new
	if index >= l.len {
		return nil
	}

	mid := l.len

	node := &Node{}
	if index <= mid {
		node = l.head
		for i := 0; i <= mid; i++ {
			if i == index {
				return node.value
			}
			node = node.next
		}
	} else {
		node = l.tail
		for i := l.len; i > mid; i-- {
			if i == index {
				return node.value
			}
			node = node.prev
		}
	}
	return nil
}

测试

func main() {
	var dl DoubleLinkedList = &List{}
	dl.Init()
	dl.PushFront(1)
	dl.PushFront(2)
	dl.PushFront(3)
	dl.PushBack(4)
	dl.PushBack(5)
	dl.PushBack(6)
	_ = dl.Insert(9, 1)
	_ = dl.Insert(9, 2)
	_ = dl.Insert(8, 5)
	_ = dl.Insert(8, 6)
	dl.RemoveFront()
	dl.RemoveBack()
	dl.Remove(1)
	dl.Remove(4)
	fmt.Println(1, dl.Get(1))
	fmt.Println(5, dl.Get(5))
	fmt.Println(3, dl.Get(3))

	fmt.Println("len", dl.Len())
	node := dl.GetHead()
	for {
		fmt.Print(node.value, " ")
		if node.next == nil {
			break
		}
		node = node.next
	}
	fmt.Print("\n")

	node = dl.GetTail()
	for {
		fmt.Print(node.value, " ")
		if node.prev == nil {
			break
		}
		node = node.prev
	}
	fmt.Print("\n")

}