1 双向链表
代码仓库
https://gitee.com/babyb/data_srtuct
根据百度百科定义:
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。
2 实现功能
双向链表与单项链表差不多, 区别就在于每个节点多了个 pre, 在删除元素的时候需要注意, 所以简单的实现以下功能
1 添加元素
2 从头向尾开始展示链表
3 从尾向头展示链表
4 删除元素
5 获取链表长度
6 判断链表是否为空
3 数据结构
空接口是指没有定义任何接口方法的接口。
没有定义任何接口方法，
意味着Go中的任意对象都可以实现空接口(因为没方法需要实现)，
任意对象都可以保存到空接口实例变量中。
type Object interface {}
type Node struct {
Data Object
pre *Node
next *Node
}
type DoubleList struct {
headNode *Node
}
4 每个具体的方法
4.1 判断链表是否为空
func (this *DoubleList) Empty() bool{
if this.headNode == nil {
return true
}else {
return false
}
}
4.2尾部添加元素
func (this *DoubleList) Add(data Object){
node := &Node{ Data: data}
cur := this.headNode
if cur == nil{
this.headNode = node
}else{
for cur.next != nil{
cur = cur.next
}
node.pre = cur
cur.next = node
}
}
4.3链表长度
func (this *DoubleList) Length() int{
count := 0;
cur := this.headNode;
if cur != nil{
for cur != nil{
cur = cur.next
count ++
}
}
return count
}
4.4 从前向后展示链表
func (this *DoubleList) ShowList(){
cur := this.headNode;
for cur != nil{
fmt.Printf("\t %v", cur.Data)
cur = cur.next
}
fmt.Println()
}
4.5从后向前展示
func (this *DoubleList) ShowListFromTail(){
tail := this.headNode;
for tail.next != nil{
tail = tail.next
}
for tail !=nil{
fmt.Printf("\t %v", tail.Data)
tail = tail.pre
}
}
4.6 移除元素
func (this *DoubleList) RemoveNode(data Object){
cur := this.headNode
if cur.Data == data{
// 移除头元素
new_head := cur.next;
new_head.pre = nil;
this.headNode = new_head
}else{
for cur !=nil{
if cur.Data == data{
// 移除元素
pre := cur.pre;
next := cur.next;
//当前节点被跳过, 会被当做垃圾回收掉
next.pre = pre;
pre.next = next
}
cur = cur.next
}
}
}
5 测试代码
package main
import (
"data_struct/0002_double_linked_list"
"fmt"
)
func main(){
list := doubleLinkedList.DoubleList{}
fmt.Println("链表是否为空" , list.Empty())
list.Add("1")
fmt.Println("链表是否为空" , list.Empty())
fmt.Println("链表长度", list.Length())
list.Add("a")
fmt.Println("链表长度", list.Length())
list.Add("b")
list.Add("+c")
list.ShowList()
//fmt.Println("从后向前展示元素")
//list.ShowListFromTail()
list.RemoveNode("b")
list.ShowList()
list.RemoveNode("1")
list.ShowList()
}
