从双向链表中的任意一个结点开始,为链表中的

作者:118kjcom开奖现场

转发请注脚出处:数据结构——Golang达成双向链表

转载请注解出处:数据结构——Golang达成单链表

118kjcom开奖现场 1Golang

118kjcom开奖现场 2118kjcom开奖现场,Golang

双向链表也叫双链表,是链表的一种,它的各样数据结点中都有七个指针,分别指向直接后继和向来四驱。所以,从双向链表中的大肆一个结点早先,都得以很有益于地拜访它的先驱结点和后继结点。

单向链表是链表的一种,其个性是链表的链接方向是单向的,对链表的拜见要通过逐条读取从头顶开首;链表是运用指针实行结构的列表;又称作结点列表,因为链表是由八个个结点组装起来的;当中各类结点都有指针成员变量指向列表中的下二个结点;列表是由结点构成,head指针指向第一个变为表头结点,而终止于尾数针对性nuLL的指针。

布局如下图:

  1. 单个结点成立充足有益,普通的线性内部存款和储蓄器平日在开创的时候就必要设定数据的轻重缓急
  2. 结点的去除特别有辅助,不供给像线性结构那样移动剩下的数量
  3. 结点的会见方便,可以透过轮回或许递归的不二法门采访到自由数据,可是平均的拜候功效低于线性表。

118kjcom开奖现场 3image.png

第一供给先定义一下链表相关的结果,SingleObject用来每种节点的多少,为interface{}结构,SingleNode为链表中的节点,SingleList单链表,为了多协程读写安全,所以在链表中加了读写锁。具体定义如下:

先是需求先定义一下链表相关的结构,DoubleObject用于每一种节点的数码,为interface{}结构,DoubleNode为链表中的节点,DoubleList双链表,为了多协程读写安全,所以在链表中加了读写锁。具体定义如下:

// 节点数据type SingleObject interface{}// 单链表节点type SingleNode struct { Data SingleObject Next *SingleNode}// 单链表type SingleList struct{ mutex *sync.RWMutex Head *SingleNode Tail *SingleNode Size uint}
// 节点数据type DoubleObject interface{}// 双链表节点type DoubleNode struct { Data DoubleObject Prev *DoubleNode Next *DoubleNode}// 双链表type DoubleList struct{ mutex *sync.RWMutex Size uint Head *DoubleNode Tail *DoubleNode}

概念实现构,接下去就须求对单链表实行先河化了。代码如下:

概念完毕构,接下去就需求对双链表举行开首化了。代码如下:

// 初始化func (list *SingleList) Init() { list.Size = 0 list.Head = nil list.Tail = nil list.mutex = new(sync.RWMutex)}
// 双链表初始化func (list *DoubleList)Init() { list.mutex = new(sync.RWMutex) list.Size = 0 list.Head = nil list.Tail = nil}

链表节点的新添分为三种,一种是在链表后边增添节点,该办法,我们誉为append;别的一种艺术是在钦定地点插入节点,大家誉为insert。其余新添时,若为第五个节点需极度处理一下。下边请看代码:

依照钦赐的职位索引,查询出节点内容。

// 添加节点到链表尾部func (list *SingleList)Append(node *SingleNode) bool { if node == nil{ return false } list.mutex.Lock() defer list.mutex.Unlock() if list.Size == 0{ list.Head = node list.Tail = node list.Size = 1 return true } tail := list.Tail tail.Next = node list.Tail = node list.Size += 1 return true}// 插入节点到指定位置func (list *SingleList)Insert(index uint, node *SingleNode) bool { if node == nil { return false } if index > list.Size{ return false } list.mutex.Lock() defer list.mutex.Unlock() if index == 0{ node.Next = list.Head list.Head = node list.Size += 1 return true } var i uint ptr := list.Head for i = 1; i < index; i ++ { ptr = ptr.Next } next := ptr.Next ptr.Next = node node.Next = next list.Size += 1 return true}
// 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}

有了新扩充功用自然就少不了删除,其它,删除节点时,要是内定的岗位是链表的头顶或尾巴部分,都亟待新鲜管理下。看代码:

链表节点的新扩充裕为三种,一种是在链表前边扩充节点,该方法,我们称为append;其余一种办法是在钦赐地方插入节点,咱们称为insert。

// 删除指定位置的节点func (list *SingleList)Delete(index uint) bool { if list == nil || list.Size == 0 || index > list.Size - 1 { return false } list.mutex.Lock() defer list.mutex.Unlock() if index == 0 { head := list.Head.Next list.Head = head if list.Size == 1{ list.Tail = nil } list.Size -= 1 return true } ptr := list.Head var i uint for i = 1; i < index; i++{ ptr = ptr.Next } next := ptr.Next ptr.Next = next.Next if index == list.Size - 1 { list.Tail = ptr } list.Size -= 1 return true}
// 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 } 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 node.Prev = nextNode.Prev node.Next = nextNode nextNode.Prev.Next = node nextNode.Prev = node list.Size++ return true}

依靠钦命的地方索引,查询出节点内容。

有了增加产量功用本来就少不了删除,别的,删除节点时,假使钦点的岗位是链表的尾部或后面部分,都亟待极度处理下。看代码:

// 获取指定位置的节点,不存在则返回nilfunc (list *SingleList)Get(index uint) *SingleNode{ if list == nil || list.Size == 0 || index > list.Size - 1 { return nil } list.mutex.RLock() defer list.mutex.RUnlock() if index == 0{ return list.Head } node := list.Head var i uint for i = 0; i < index; i ++ { node = node.Next } return node}
// 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 node.Prev.Next = node.Next node.Next.Prev = node.Prev list.Size-- return true}

最后,大家扩大三个打字与印刷链表的效应,方便大家看一切链表的剧情:

最后,大家扩展一个打字与印刷链表的功用,方便我们看整个链表的内容,这里扩展了两种打字与印刷格局,三个是坚定不移打字与印刷,另二个是从尾到头打印:

// 输出链表func (list *SingleList)Display(){ if list == nil { fmt.Println("this single list is nil") return } list.mutex.RLock() defer list.mutex.RUnlock() fmt.Printf("this single list size is %d n", list.Size) ptr := list.Head var i uint for i = 0; i < list.Size; i++{ fmt.Printf("No%3d data is %vn", i + 1, ptr.Data) ptr = ptr.Next }}
// 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 %vn", 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 %vn", ptr.Data) ptr = ptr.Prev }}

github源码

github源码

转发请评释出处: 数据结构——Golang实现单链表

转载请表明出处: 数据结构——Golang实现双向链表

本文由118kjcom最快开奖现场发布,转载请注明来源

关键词: