双向链表结构如下图
代码实现
package line
type DoubleLinkList struct {
first *doubleLinkElement
length int
}
type doubleLinkElement struct {
item interface{}
prev *doubleLinkElement
next *doubleLinkElement
}
func NewDoubleLinkList() *DoubleLinkList {
return &DoubleLinkList{}
}
func (this *DoubleLinkList) 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 *DoubleLinkList) Insert(index int, item interface{}) bool {
if index > this.length || index < 0 {
return false
}
defer func() {
this.length++
}()
current := &doubleLinkElement{
item: item,
}
//头位置,需要更换头指针
if index == 0 {
if this.first != nil {
current.next = this.first
this.first.prev = current
}
this.first = current
return true
}
ele := this.first
for i := 0; i < index-1; i++ {
ele = ele.next
}
//将索引位置的上一元素变为当前元素的上一元素
current.prev = ele
//将索引位置元素变为当前元素的下一元素
current.next = ele.next
if ele.next != nil && ele.next.next != nil {
//索引位置下一元素的上个元素变为当前元素
ele.next.next.prev = current
}
//索引位置上一元素的下个元素变为当前元素
ele.next = current
return true
}
func (this *DoubleLinkList) Lpush(item interface{}) {
this.Insert(0, item)
}
func (this *DoubleLinkList) Rpush(item interface{}) {
this.Insert(this.length, item)
}
func (this *DoubleLinkList) Set(index int, item interface{}) bool {
if index > this.length || index < 0 {
return false
}
current := &doubleLinkElement{
item: item,
}
if index == 0 {
if this.length == 0 {
this.length++
} else {
current.next = this.first.next
if this.first.next != nil {
this.first.next.prev = current
}
}
this.first = current
return true
}
ele := this.first
for i := 0; i < index-1; i++ {
ele = ele.next
}
current.prev = ele
if ele.next == nil {
this.length++
ele.next = current
return true
}
ele.next = current
current.next = ele.next.next
ele.next.prev = current
return true
}
func (this *DoubleLinkList) Length() int {
return this.length
}
func (this *DoubleLinkList) Remove(index int) *doubleLinkElement {
if this.length == 0 || index > this.length-1 || index < 0 {
return nil
}
defer func() {
this.length--
}()
ele := this.first
if index == 0 {
this.first = this.first.next
if this.first != nil {
this.first.prev = nil
}
return ele
}
for i := 0; i < index; i++ {
ele = ele.next
}
ele.prev.next = ele.next
if ele.next != nil {
ele.next.prev = ele.prev
}
return ele
}
func (this *DoubleLinkList) Lpop() *doubleLinkElement {
return this.Remove(0)
}
func (this *DoubleLinkList) Rpop() *doubleLinkElement {
return this.Remove(this.length - 1)
}
func (this *DoubleLinkList) Range(f func(index int, item interface{})) {
ele := this.first
for i := 0; i < this.length; i++ {
f(i, ele.item)
ele = ele.next
}
}
测试
package line
import (
"testing"
"time"
)
func TestDoubleLinkList_Insert(t *testing.T) {
double := NewDoubleLinkList()
result := double.Insert(1, time.Now().Unix())
if result {
t.Fatalf("want false, got %#v", result)
}
result = double.Insert(0, 1)
if !result {
t.Fatalf("want true, got %#v", result)
}
length := double.Length()
if length != 1 {
t.Fatalf("want 1, got %#v", length)
}
result = double.Insert(0, 2)
if !result {
t.Fatalf("want true, got %#v", result)
}
result = double.Insert(1, 3)
if !result {
t.Fatalf("want true, got %#v", result)
}
length = double.Length()
if length != 3 {
t.Fatalf("want 3, got %#v", length)
}
r0, _ := double.Get(0)
if r0 != 2 {
t.Fatalf("want 2, got %#v", r0)
}
r1, _ := double.Get(1)
if r1 != 3 {
t.Fatalf("want 3, got %#v", r1)
}
r2, _ := double.Get(2)
if r2 != 1 {
t.Fatalf("want 2, got %#v", r2)
}
}
func TestDoubleLinkList_Pushpop(t *testing.T) {
double := NewDoubleLinkList()
double.Lpush(5)
double.Lpush(4)
double.Lpush(3)
double.Lpush(2)
double.Lpush(1)
double.Rpush(6)
double.Rpush(7)
double.Rpush(8)
double.Rpush(9)
double.Rpush(10)
for i := 1; i < 11; i++ {
item := double.Lpop()
if item.item.(int) != i {
t.Fatalf("want %d; got %#v", i, item.item)
}
}
if double.Length() != 0 {
t.Fatalf("want 0, got %#v", double.Length())
}
double.Range(func(index int, item interface{}) {
t.Fatalf("not run")
})
double.Rpush(6)
double.Rpush(7)
double.Rpush(8)
double.Rpush(9)
double.Rpush(10)
if double.Length() != 5 {
t.Fatalf("want 5, got %#v", double.Length())
}
for i := 10; i > 5; i-- {
item := double.Rpop()
if item.item.(int) != i {
t.Fatalf("want %d; got %#v", i, item.item)
}
}
if double.Length() != 0 {
t.Fatalf("want 0, got %#v", double.Length())
}
}
func TestDoubleLinkList_Set(t *testing.T) {
double := NewDoubleLinkList()
double.Set(0, 0)
double.Set(1, 1)
double.Set(2, 2)
double.Set(3, 3)
for i := 0; i < 4; i++ {
item := double.Lpop()
if item.item.(int) != i {
t.Fatalf("want %d; got %#v", i, item.item)
}
}
}
时间复杂度
操作 | 最好时间复杂度 | 最差时间复杂度 |
---|---|---|
查询 | O(n) | O(n) |
删除 | O(1) | O(n) |
插入 | O(1) | O(n) |
修改 | O(1) | O(n) |