重学数据结构与算法（6）

这是我参与8月更文挑战的第6天，活动详情查看：8月更文挑战

双向链表

双向链表也是链表的一种，比单向链表复杂一点，单向链表只能从头部遍历到尾部，单向每个节点只保存下一个节点的内存地址。双向链表每个节点比单向链表多存放一个数据就是存放前一个节点的内存地址，双向链表可以提升链表的综合性能。
这样双向链表每一个节点就有三个部分组成，查找元素的时候可以根据元素的位置来判断从头部开始遍历查找还是从尾部开始遍历查找。

定义一个双向链表结构

package main

import "fmt"

type DoubleObject interface{}

// 双链表节点
type DoubleLinkNode struct {
	value DoubleObject
	prev  *DoubleLinkNode //上个节点的内存地址
	next  *DoubleLinkNode //下个节点的内存地址
}

//双链表结构
type DoubleLinkList struct {
	head   *DoubleLinkNode
	length int
}

//初始化一个新的node节点
func NewNode(value interface{}) *DoubleLinkNode {
	return &DoubleLinkNode{value, nil, nil}
}

func (node *DoubleLinkNode) Value() interface{} {
	return node.value
}

func (node *DoubleLinkNode) Prev() *DoubleLinkNode {
	return node.prev
}

func (node *DoubleLinkNode) Next() *DoubleLinkNode {
	return node.next
}

//新建一个双链表结构
func NewDoubleLinkList() *DoubleLinkList {
	head := NewNode(nil)
	return &DoubleLinkList{head, 0}
}

//获取双链表的长度
func (dlist *DoubleLinkList) GetLength() int {
	return dlist.length
}

//返回第一个节点的数据
func (dlist *DoubleLinkList) GetFirstNodeValue() *DoubleLinkNode {
	return dlist.head.next
}

//头部插入
func (dlist *DoubleLinkList) InsertHead(node *DoubleLinkNode) {
	phead := dlist.head //头节点
	if phead.next == nil {
		//假如当前头节点的下一个节点为空，直接插入
		node.next = nil
		phead.next = node //把头节点的下一个节点指向新插入的节点
		node.prev = phead //上一个节点

		dlist.length++ //长度始终加一
	} else {
		//假如当前头节点的下一个节点不为空，直接插入
		phead.next.prev = node //指定当前头节点的上一个节点的位置为插入的这个节点
		node.next = phead.next
		phead.next = node
		node.prev = phead
		dlist.length++ //插入方法长度始终加一
	}
}

//尾部插入
func (dlist *DoubleLinkList) InsertTail(node *DoubleLinkNode) {
	phead := dlist.head    //头节点
	if phead.next == nil { //在链表最后插入元素必须循环链表到最后一个节点，为空直接插
		node.next = nil //插入的最后一个节点的下一个肯定为空
		phead.next = node
		node.prev = phead
		dlist.length++ //插入方法长度始终加一

	} else {
		for phead.next != nil { //在链表最后插入元素必须循环链表到最后一个节点
			phead = phead.next
		}
		phead.next = node
		node.prev = phead
		dlist.length++ //插入方法长度始终加一
	}
}

//显示双向链表
func (dlist *DoubleLinkList) String() string {
	var forwardString string //正向循环结果字符串
	var reverseString string //反向循环结果字符串
	phead := dlist.head
	for phead.next != nil {
		forwardString += fmt.Sprintf("%v-->", phead.next.value)
		phead = phead.next
	}
	forwardString += fmt.Sprintf("nil")
	forwardString += "\n"
	for phead != dlist.head {
		reverseString += fmt.Sprintf("<--%v", phead.value)
		phead = phead.prev
	}
	reverseString += fmt.Sprintf("nil")
	reverseString += "\n"
	return forwardString + reverseString + "\n"
}

//测试节点头插与尾插和打印
func main() {
	dlist := NewDoubleLinkList()
	node1 := NewNode(1)
	node2 := NewNode(2)
	node3 := NewNode(3)
	node4 := NewNode(4)
	node5 := NewNode(5)
	dlist.InsertHead(node1)
	dlist.InsertHead(node2)
	dlist.InsertHead(node3)
	dlist.InsertTail(node4)
	dlist.InsertTail(node5)
	fmt.Println(dlist.String())

}
复制代码

打印的结果为：

3-->2-->1-->4-->5-->nil
<--5<--4<--1<--2<--3nil

复制代码

总结

双向链表还是比较复杂，代码较多，没有画图，还是少点灵魂。这里简单做了一个初始化和插入的代码，对于双向链表的删，改，查，我们下篇再研究。