# 数据结构——Golang实现双向链表

ChainZhang · · 5027 次点击 · · 开始浏览

Golang

image.png

# 2. Golang 实现

## 2.1. 相关结构体

``````// 节点数据
type DoubleObject interface{}

// 双链表节点
type DoubleNode struct {
Data DoubleObject
Prev *DoubleNode
Next *DoubleNode
}

// 双链表
type DoubleList struct{
mutex *sync.RWMutex
Size uint
Tail *DoubleNode
}
``````

## 2.2. 链表初始化

``````// 双链表初始化
func (list *DoubleList)Init()  {
list.mutex = new(sync.RWMutex)
list.Size = 0
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{
}
var i uint
for i = 1; i <= index; i ++{
node = node.Next
}
return node
}
``````

## 2.4. 新增节点

``````// 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.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{
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.Tail = nil
} else {
}
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)
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
}
}
``````

github源码

# 完

0 回复

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

Golang

image.png

# 2. Golang 实现

## 2.1. 相关结构体

``````// 节点数据
type DoubleObject interface{}

// 双链表节点
type DoubleNode struct {
Data DoubleObject
Prev *DoubleNode
Next *DoubleNode
}

// 双链表
type DoubleList struct{
mutex *sync.RWMutex
Size uint
Tail *DoubleNode
}
``````

## 2.2. 链表初始化

``````// 双链表初始化
func (list *DoubleList)Init()  {
list.mutex = new(sync.RWMutex)
list.Size = 0
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{
}
var i uint
for i = 1; i <= index; i ++{
node = node.Next
}
return node
}
``````

## 2.4. 新增节点

``````// 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.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{
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.Tail = nil
} else {
}
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)
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
}
}
``````

github源码