链表是一种链式存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的,单链表的结构如下图
代码实现
package line
type LinkList struct {
first *element
last *element
length int
}
type element struct {
item interface{}
next *element
}
func NewLinkList() *LinkList {
return &LinkList{}
}
func (this *LinkList) Get(index int) (interface{}, bool) {
if this.length == 0 || index >= this.length || index < 0 {
return nil, false
}
ele := this.first
for i := 0; i < index; i++ {
ele = ele.next
if ele == nil {
return nil, false
}
}
return ele.item, true
}
func (this *LinkList) Set(index int, item interface{}) bool {
if index > this.length || index < 0 {
return false
}
current := &element{
item: item,
}
if index == 0 {
current.next = this.first.next
this.first = current
if this.length == 0 {
this.last = this.first
this.length++
}
return true
}
ele := this.first
for i:=0; i< index -1; i++ {
ele = ele.next
}
indexEle := ele.next
current.next = indexEle.next
ele.next = current
if index == this.length {
this.length++
this.last = current
}
return true
}
func (this *LinkList) Insert(index int, item interface{}) bool {
if index > this.length || index < 0 {
return false
}
defer func() {
this.length++
}()
current := &element{
item: item,
}
//头位置,需要更换头指针
if index == 0 {
current.next = this.first
this.first = current
if this.length == 0 {
this.last = this.first
}
return true
}
//尾位置,需要更换尾指针
if index == this.length {
this.last.next = current
this.last = current
return true
}
ele := this.first
for i := 0; i < index - 1; i++ {
ele = ele.next
}
//获取索引位置元素
indexEle := ele.next
//将索引位置元素放到插入元素后面
current.next = indexEle
//上一元素的下一个元素为当前元素
ele.next = current
return true
}
func (this *LinkList) Prepend(item interface{}) {
this.Insert(0, item)
}
func (this *LinkList) Append(item interface{}) {
this.Insert(this.length, item)
}
func (this *LinkList) Length() int {
return this.length
}
func (this *LinkList) Remove(index int) bool {
if this.length == 0 || index > this.length - 1 || index < 0 {
return false
}
defer func() {
this.length--
}()
if index == 0 {
this.first = this.first.next
return true
}
ele := this.first
for i :=0; i < index - 1; i++ {
ele = ele.next
}
indexEle := ele.next
ele.next = indexEle.next
indexEle = nil
if this.length == index {
this.last = ele
}
return true
}
func (this *LinkList) Range(f func(index int, item interface{})) {
ele := this.first
for i := 0; i < this.length; i++ {
f(i, ele.item)
ele = ele.next
}
}
使用
//初始化链表
container := line.NewLinkList()
//向索引位置1插入数据10,插入失败,因为头结点还没有数据
result := container.Insert(1, 10)
fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
//向头结点插入数据0
//此时数据为:0
result = container.Insert(0, 0)
fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
//向索引为8插入数据80,插入失败
//此时数据为:0
result = container.Insert(8, 80)
fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
//此时数据为:10 0
result = container.Insert(0, 10)
fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
container.Range(func(index int, item interface{}) {
fmt.Printf("index:%d; item:%v\n", index, item)
})
//此时数据为:10 20 0
result = container.Insert(1, 20)
fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
//此时数据为:10 20 0 30
container.Append(30)
fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
//此时数据为:50 10 20 0 30
container.Prepend(50)
fmt.Printf("Insert: %t, container.Length:%d\n", result, container.Length())
container.Range(func(index int, item interface{}) {
fmt.Printf("index:%d; item:%v\n", index, item)
})
container.Append(60)
container.Append(70)
container.Append(80)
container.Append(90)
container.Append(100)
container.Append(110)
//单链表无长度限制
fmt.Printf("container.Length:%d\n", container.Length())
for i :=0; i < container.Length(); i++ {
value, _ := container.Get(i)
fmt.Printf("i:%d; item: %v\n", i, value)
}
//删除
container.Remove(0)
value, _ := container.Get(0)
fmt.Printf("i:%d; item: %v\n", 0, value)
container.Set(9, 999)
value, _ = container.Get(9)
fmt.Printf("i:%d; item: %v\n", 9, value)
以上例程运行结果
Insert: false, container.Length:0
Insert: true, container.Length:1
Insert: false, container.Length:1
Insert: true, container.Length:2
index:0; item:10
index:1; item:0
Insert: true, container.Length:3
Insert: true, container.Length:4
Insert: true, container.Length:5
index:0; item:50
index:1; item:10
index:2; item:20
index:3; item:0
index:4; item:30
container.Length:11
i:0; item: 50
i:1; item: 10
i:2; item: 20
i:3; item: 0
i:4; item: 30
i:5; item: 60
i:6; item: 70
i:7; item: 80
i:8; item: 90
i:9; item: 100
i:10; item: 110
i:0; item: 10
i:9; item: 999
时间复杂度
操作 | 最好时间复杂度 | 最差时间复杂度 |
---|---|---|
查询 | O(n) | O(n) |
删除 | O(1) | O(n) |
插入 | O(1) | O(n) |
修改 | O(1) | O(n) |