单链表
- 拥有头节点
- 每个节点有两个字段
data : 存储数据
next : 指向下一个节点的指针
上代码 :
package link
import (
"fmt"
)
// 单向链表
type IOneWayLinkList interface {
InsertOnHead(value int) //从链表头部插入
InsertOnEnd(value int) //从尾部添加元素
InsertOnIndex(value int, index int) //在指定位置添加元素 index是下标,从0开始,
DelDataOnIndex(index int) //删除链表指定位置的节点, index是下标,从0开始
DelData(value int) //删除链表指定值的节点
PrintLink() //打印链表所有节点
FindValue(value int) bool //查询链表中是否包含某个值
UpdateValueByIndex(index int, value int) //根据index修改值为value, index是下标,从0开始
}
// Node 节点
type Node struct {
data int // 节点数据
next *Node
}
// List 链表
type List struct {
head *Node // 头节点
length uint64 // 链表长度
}
func InitOneWayLinkList() IOneWayLinkList {
return &List{
head: nil,
length: 0,
}
}
func (l *List) InsertOnHead(value int) {
n := &Node{
data: value,
next: nil,
}
if l.head == nil {
l.head = n
l.length++
fmt.Println("InsertOnHead success, this head")
return
}
n.next = l.head
l.head = n
l.length++
fmt.Println("InsertOnHead success")
}
func (l *List) InsertOnEnd(value int) {
n := &Node{
data: value,
next: nil,
}
if l.head == nil {
l.head = n
l.length++
fmt.Println("InsertOnEnd success, this head")
return
}
cur := l.head
for cur.next != nil {
cur = cur.next
}
// 找到链表尾部了
cur.next = n
l.length++
fmt.Println("InsertOnEnd success")
}
func (l *List) InsertOnIndex(value int, index int) {
if index < 0 {
fmt.Println("InsertOnIndex error, index error")
return
}
n := &Node{
data: value,
next: nil,
}
if l.head == nil {
l.head = n
l.length++
fmt.Println("InsertOnIndex success")
return
}
if index == 0 {
l.InsertOnHead(value)
}
i := 1
cur := l.head
for cur.next.next != nil {
if i == index {
n.next = cur.next
cur.next = n
l.length++
fmt.Println("InsertOnIndex success")
return
}
i++
cur = cur.next
}
// 走到这里 cur.next.next 为nil, 说明可能要插在链表尾部的前一个, cur.next是最后一个元素
if i == index {
n.next = cur.next
cur.next = n
l.length++
fmt.Println("InsertOnIndex success")
} else {
fmt.Println("InsertOnIndex error, index error")
}
}
func (l *List) DelDataOnIndex(index int) {
if index < 0 {
fmt.Println("DelDataOnIndex error, index < 0, error")
return
}
// 删除头节点
if index == 0 {
l.head = l.head.next
l.length--
fmt.Println("DelDataOnIndex success, is head")
return
}
i := 1
cur := l.head
for cur.next.next != nil {
if i == index {
cur.next = cur.next.next
l.length--
fmt.Println("DelDataOnIndex success, index:", index)
return
}
i++
cur = cur.next
}
// 到了这里,说明 cur.next.next == nil, 可能要删除最后一个, cur.next是最后一个元素
if i == index {
cur.next = cur.next.next
l.length--
fmt.Println("DelDataOnIndex success, index:", index)
} else {
fmt.Println("DelDataOnIndex error, index not found")
}
}
func (l *List) DelData(value int) {
// 先看是不是要删除头节点
cur := l.head
if cur.data == value {
l.head = l.head.next
l.length--
fmt.Println("DelData success, value:", value)
return
}
// 找下一个
for cur.next.next != nil {
if cur.next.data == value {
cur.next = cur.next.next
l.length--
fmt.Println("DelData success, value:", value)
return
}
cur = cur.next
}
// 到了这里,说明 cur.next.next == nil, 可能要删除最后一个, cur.next是最后一个元素
if cur.next.data == value {
cur.next = cur.next.next
l.length--
fmt.Println("DelData success, value:", value)
} else {
fmt.Println("DelData fail, value not found")
}
}
func (l *List) PrintLink() {
if l.head == nil {
fmt.Println("list is nil")
return
}
cur := l.head
count := 0
for cur != nil {
fmt.Println("node data:", cur.data, ", index:", count)
cur = cur.next
count++
}
fmt.Println("link length:", l.length)
}
func (l *List) FindValue(value int) bool {
cur := l.head
for cur != nil {
if cur.data == value {
return true
}
cur = cur.next
}
return false
}
func (l *List) UpdateValueByIndex(index int, value int) {
if index < 0 {
fmt.Println("UpdateValueByIndex fail, index < 0")
return
}
i := 0
cur := l.head
for cur != nil {
if i == index {
old := cur.data
cur.data = value
fmt.Println("UpdateValueByIndex success,", old, "->", value)
return
}
i++
cur = cur.next
}
fmt.Println("UpdateValueByIndex fail, index not found")
}
测试代码:
// TestOneWayLinkList 测试单向链表
func TestOneWayLinkList() {
list := link.InitOneWayLinkList()
list.InsertOnHead(1)
list.InsertOnHead(2)
list.InsertOnHead(3)
list.InsertOnHead(4)
list.PrintLink()
list.InsertOnEnd(5)
list.InsertOnEnd(6)
list.InsertOnEnd(12)
list.PrintLink()
list.InsertOnIndex(33, 4)
list.PrintLink()
list.DelDataOnIndex(5)
list.PrintLink()
list.DelDataOnIndex(45)
list.PrintLink()
list.DelData(1)
list.PrintLink()
value := 33
res := list.FindValue(value)
if res {
fmt.Println("list found value:", value)
} else {
fmt.Println("list not found value:", value)
}
value2 := 46
list.UpdateValueByIndex(5, value2)
list.PrintLink()
list.UpdateValueByIndex(12, value2)
list.PrintLink()
}
双向循环链表
- pre:上一个节点,next:下一个节点
- 头节点的 pre 指向尾节点
- 尾节点的 next 指向头节点
上代码:
import "fmt"
// 双向循环链表
// 代码的index是从1开始算
type DoubleNode struct {
data int
next *DoubleNode
pre *DoubleNode
}
type DoubleListInterface interface {
InsertHead(value int) // 头部插入
InsertTail(value int) // 尾部插入
InsertByIndex(value int, index int) // 根据位置插入 index是从1开始算
DeleteByIndex(index int) // 根据位置删除 index是从1开始算
DeleteByValue(value int) // 根据值删除
UpdateByIndex(index int, newValue int) // 根据位置修改 index是从1开始算
UpdateByValue(oldValue int, newValue int) // 根据值删除
GetIndexByValue(value int) (int, bool) // 根据值获取位置 只有一种错误可能,就返回bool
GetValueByIndex(index int) (int, bool) // 根据位置获取值
PrintList()
}
type DoubleList struct {
head *DoubleNode
tail *DoubleNode
length int
}
func NewDoubleList() *DoubleList {
return &DoubleList{
head: nil,
tail: nil,
length: 0,
}
}
func (d *DoubleList) InsertHead(value int) {
newData := &DoubleNode{
data: value,
next: nil,
pre: nil,
}
if d.head == nil {
// 链表没有数据
d.head = newData
d.tail = newData
newData.next = newData
newData.pre = newData
} else {
// 链表有数据
newData.next = d.head
newData.pre = d.tail
d.tail.next = newData
d.head.pre = newData
d.head = newData
}
d.length++
}
func (d *DoubleList) InsertTail(value int) {
newNode := &DoubleNode{
data: value,
next: nil,
pre: nil,
}
if d.head == nil {
// 链表没有数据
d.head = newNode
d.tail = newNode
newNode.next = newNode
newNode.pre = newNode
} else {
// 链表有数据
newNode.pre = d.tail
newNode.next = d.head
d.tail.next = newNode
d.head.pre = newNode
d.tail = newNode
}
d.length++
}
func (d *DoubleList) InsertByIndex(value int, index int) {
if index > d.length || index <= 0 {
fmt.Println("index error")
return
}
newNode := &DoubleNode{
data: value,
next: nil,
pre: nil,
}
if d.head == nil {
d.InsertHead(value)
return
}
if index == d.length {
d.InsertTail(value)
}
cur := d.head
// cur指向头节点的时候, count=1
count := 1
for cur != d.tail {
if count == index {
newNode.next = cur
newNode.pre = cur.pre
cur.pre.next = newNode
cur.pre = newNode
d.length++
}
cur = cur.next
count++
}
}
func (d *DoubleList) DeleteByIndex(index int) {
if d.head == nil {
fmt.Println("link nil")
return
}
if index > d.length || index <= 0 {
fmt.Println("index error")
return
}
if d.head == d.tail {
// 只有一个节点
d.head = nil
d.tail = nil
d.length = 0
return
}
cur := d.head
// cur指向头节点的时候, count=1
count := 1
fmt.Println("DeleteByIndex:", index)
// 当cur转了一圈回到头节点时候,count肯定不等于1,退出循环
for cur != d.head || count == 1 {
if count == index {
cur.pre.next = cur.next
cur.next.pre = cur.pre
if index == d.length {
// 重新指定尾节点
d.tail = cur.pre
}
if index == 1 {
// 重新指定头节点
d.head = cur.next
}
// 删除当前节点的前后指向关系,让它与链表失去关联,则会被GC回收
cur.next = nil
cur.pre = nil
d.length--
return
}
cur = cur.next
count++
if count > d.length {
// 说明已经遍历完链表了
break
}
}
fmt.Println("DeleteByIndex error")
}
func (d *DoubleList) DeleteByValue(value int) {
if d.head == nil {
fmt.Println("link is nil")
return
}
cur := d.head
count := 1
fmt.Println("DeleteByValue:", value)
// 当cur转了一圈回到头节点时候,count肯定不等于1,退出循环
for cur != d.head || count == 1 {
if value == cur.data {
cur.pre.next = cur.next
cur.next.pre = cur.pre
if count == d.length {
// 重新指定尾节点
d.tail = cur.pre
}
if count == 1 {
// 重新指定头节点
d.head = cur.next
}
// 删除当前节点的前后指向关系,让它与链表失去关联,则会被GC回收
cur.next = nil
cur.pre = nil
d.length--
return
}
cur = cur.next
count++
if count > d.length {
// 说明已经遍历完链表了
break
}
}
fmt.Println("DeleteByValue error")
}
func (d *DoubleList) UpdateByIndex(index int, newValue int) {
if index > d.length || index <= 0 {
fmt.Println("index error")
return
}
cur := d.head
count := 1
fmt.Println("UpdateByIndex:", index, ", change to:", newValue)
// 当cur转了一圈回到头节点时候,count肯定不等于1,退出循环
for cur != d.head || count == 1 {
if count == index {
cur.data = newValue
return
}
cur = cur.next
count++
if count > d.length {
// 说明已经遍历完链表了
break
}
}
fmt.Println("UpdateByIndex error")
}
func (d *DoubleList) UpdateByValue(oldValue int, newValue int) {
cur := d.head
count := 1
fmt.Println("UpdateByValue oldValue:", oldValue, ", change to:", newValue)
// 当cur转了一圈回到头节点时候,count肯定不等于1,退出循环
for cur != d.head || count == 1 {
if oldValue == cur.data {
cur.data = newValue
return
}
cur = cur.next
count++
if count > d.length {
// 说明已经遍历完链表了
break
}
}
fmt.Println("UpdateByValue error")
}
func (d *DoubleList) GetIndexByValue(value int) (int, bool) {
cur := d.head
count := 1
// 当cur转了一圈回到头节点时候,count肯定不等于1,退出循环
for cur != d.head || count == 1 {
if value == cur.data {
// 找到了
return count, true
}
cur = cur.next
count++
if count > d.length {
// 说明已经遍历完链表了
break
}
}
return 0, false
}
func (d *DoubleList) GetValueByIndex(index int) (int, bool) {
if index > d.length || index <= 0 {
return 0, false
}
cur := d.head
count := 1
// 当cur转了一圈回到头节点时候,count肯定不等于1,退出循环
for cur != d.head || count == 1 {
if index == count {
return cur.data, true
}
cur = cur.next
count++
if count > d.length {
// 说明已经遍历完链表了
break
}
}
return 0, false
}
func (d *DoubleList) PrintList() {
if d.head == nil {
fmt.Println("list is null")
return
}
cur := d.head
count := 1
for {
//先打印再判断
fmt.Println("node data:", cur.data, ",index:", count,
",next data:", cur.next.data,
",pre data:", cur.pre.data)
if cur.next == d.head {
break
}
cur = cur.next
count++
}
fmt.Println("list length =", d.length)
}
测试代码:
// TestDoubleLinkList 测试双向循环链表
func TestDoubleLinkList() {
list := link.NewDoubleList()
list.InsertHead(4)
list.InsertHead(3)
list.InsertHead(2)
list.InsertHead(1)
list.PrintList()
list.InsertTail(5)
list.InsertTail(6)
list.InsertTail(7)
list.PrintList()
list.InsertByIndex(16, 5)
list.PrintList()
list.DeleteByIndex(3)
list.PrintList()
list.DeleteByValue(6)
list.PrintList()
list.UpdateByIndex(1, 11)
list.UpdateByIndex(6, 66)
list.PrintList()
list.UpdateByValue(11, 111)
list.UpdateByValue(66, 666)
list.UpdateByValue(2, 22)
list.UpdateByValue(232, 444)
list.PrintList()
v1 := 666
index, ok := list.GetIndexByValue(v1)
if !ok {
fmt.Println("GetIndexByValue error, value:", v1, "not exist")
} else {
fmt.Println("GetIndexByValue value:", v1, ",index:", index)
}
v2 := 4343
index, ok = list.GetIndexByValue(v2)
if !ok {
fmt.Println("GetIndexByValue error, value:", v2, "not exist")
} else {
fmt.Println("GetIndexByValue value:", v2, ",index:", index)
}
v3 := 6
value, ok := list.GetValueByIndex(v3)
if !ok {
fmt.Println("GetValueByIndex error, index:", v3, "invalid")
} else {
fmt.Println("GetValueByIndex index:", v3, ",value:", value)
}
v4 := 8
value, ok = list.GetValueByIndex(v4)
if !ok {
fmt.Println("GetValueByIndex error, index:", v4, "invalid")
} else {
fmt.Println("GetValueByIndex index:", v4, ",value:", value)
}
}