内容简介:转载请注明出处:双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。结构如下图:
转载请注明出处: 数据结构——Golang实现双向链表
Golang
1. 双向链表
双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。
结构如下图:
image.png
2. Golang 实现
2.1. 相关结构体
首先需要先定义一下链表相关的结构,DoubleObject用于每个节点的数据,为interface{}结构,DoubleNode为链表中的节点,DoubleList双链表,为了多协程读写安全,所以在链表中加了读写锁。
具体定义如下:
// 节点数据 type DoubleObject interface{} // 双链表节点 type DoubleNode struct { Data DoubleObject Prev *DoubleNode Next *DoubleNode } // 双链表 type DoubleList struct{ mutex *sync.RWMutex Size uint Head *DoubleNode Tail *DoubleNode }
2.2. 链表初始化
定义完结构,接下来就需要对双链表进行初始化了。代码如下:
// 双链表初始化 func (list *DoubleList)Init() { list.mutex = new(sync.RWMutex) list.Size = 0 list.Head = nil list.Tail = nil }
2.3. 查询节点
根据指定的位置索引,查询出节点内容。
// Get 获取指定位置的节点 func (list *DoubleList)Get(index uint) *DoubleNode { if list.Size == 0 || index > list.Size - 1 { return nil } if index == 0{ return list.Head } node := list.Head var i uint for i = 1; i <= index; i ++{ node = node.Next } return node }
2.4. 新增节点
链表节点的新增分为两种,一种是在链表后面追加节点,该方式,我们称为append;另外一种方式是在指定位置插入节点,我们叫做insert。
// Append 向双链表后面追加节点 func (list *DoubleList)Append(node *DoubleNode) bool { if node == nil{ return false } list.mutex.Lock() defer list.mutex.Unlock() if list.Size == 0 { list.Head = node list.Tail = node node.Next = nil node.Prev = nil } else { node.Prev = list.Tail node.Next = nil list.Tail.Next = node list.Tail = node } list.Size++ return true } // Insert 向双链表指定位置插入节点 func (list *DoubleList)Insert(index uint, node *DoubleNode) bool { if index > list.Size || node == nil{ return false } if index == list.Size{ return list.Append(node) } list.mutex.Lock() defer list.mutex.Unlock() if index == 0{ node.Next = list.Head list.Head = node list.Head.Prev = nil list.Size++ return true } nextNode := list.Get(index) node.Prev = nextNode.Prev node.Next = nextNode nextNode.Prev.Next = node nextNode.Prev = node list.Size++ return true }
2.5. 删除节点
有了新增功能自然就少不了删除,此外,删除节点时,如果指定的位置是链表的头部或尾部,都需要特殊处理下。看代码:
// Delete 删除指定位置的节点 func (list *DoubleList) Delete (index uint) bool { if index > list.Size - 1 { return false } list.mutex.Lock() defer list.mutex.Unlock() if index == 0 { if list.Size == 1{ list.Head = nil list.Tail = nil } else { list.Head.Next.Prev = nil list.Head = list.Head.Next } list.Size-- return true } if index == list.Size - 1{ list.Tail.Prev.Next = nil list.Tail = list.Tail.Prev list.Size-- return true } node := list.Get(index) node.Prev.Next = node.Next node.Next.Prev = node.Prev list.Size-- return true }
2.6. 打印链表
最后,我们增加一个打印链表的功能,方便我们看整个链表的内容,这里增加了两种打印方法,一个是从头到尾打印,另一个是从尾到头打印:
// Display 打印双链表信息 func (list *DoubleList)Display(){ if list == nil || list.Size == 0 { fmt.Println("this double list is nil or empty") return } list.mutex.RLock() defer list.mutex.RUnlock() fmt.Printf("this double list size is %d \n", list.Size) ptr := list.Head for ptr != nil { fmt.Printf("data is %v\n", ptr.Data) ptr = ptr.Next } } // Reverse 倒序打印双链表信息 func (list *DoubleList)Reverse(){ if list == nil || list.Size == 0 { fmt.Println("this double list is nil or empty") return } list.mutex.RLock() defer list.mutex.RUnlock() fmt.Printf("this double list size is %d \n", list.Size) ptr := list.Tail for ptr != nil { fmt.Printf("data is %v\n", ptr.Data) ptr = ptr.Prev } }
3. 源码
完
转载请注明出处: 数据结构——Golang实现双向链表
以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网
猜你喜欢:本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。