```
package main
/* 双向链表结构体*/
type DuLNodestruct{
valinterface{}
prefix *DuLNode// 前一个节点
rear *DuLNode// 后一个节点
}
/* 初始化双向链表*/
func (L *DuLNode) IninDul() {
L.val = nil
L.prefix = nil
L.rear = nil
}
/* 清空双向链表*/
func (L *DuLNode) ClearDul() {
L.IninDul()
}
/* 删除双向链表*/
func (L *DuLNode) DeleteDul() {
L.IninDul()
}
/* 获取第i个结点的值*/
func (L *DuLNode) GetVal(i uint32)interface{} {
return L.val
}
/* 获取双向链表的长度*/
func (L *DuLNode) Length() uint32 {
// 双向链表为空
if L.prefix == nil {
return 0
}
p := L
length := uint32(1)
for p.rear != L {
length +=1
p = p.rear
}
return length
}
/* 在第i个节点插入数据*/
func (L *DuLNode) Insert(i uint32, einterface{}) {
length := L.Length()
// 双向链表为空
if length ==0 {
L.val, L.rear, L.prefix = e, L, L
return
}
p := DuLNode{e, nil, nil}
// 末尾插入一个数据
if i > length +1 {
p.rear = L.rear
L.rear.prefix = &p
p.prefix = L
return
}
// 头部插入一个数据
if i <=1 {
L.rear.prefix = &p
p.rear = L.rear
p.prefix = L
L = &p
return
}
// 其他位置插入数据,n的位置为要插入的位置前一个位置节点
n := L
for j := uint32(2);j < i;j +=1 {
n = n.rear
}
p.rear = n
n.prefix = &p
p.prefix = n
}
/* 在第i个节点删除数据,返回删除所在位置的值*/
func (L *DuLNode) Delete(i uint32)interface{} {
length := L.Length()
// 双向链表的长度等于0
if length ==0 {
return nil
}
if i <1 {
// 删除头部节点
L.rear.prefix = L.prefix
L.prefix.rear = L.rear
res := L.val
L = L.prefix
return res
}else if i > length {
// 删除末尾元素
i = length
res := L.rear.val
L.rear.rear.prefix = L
L.rear = L.rear.rear
return res
}
n := L
for j := uint32(2);j < i;j +=1 {
n = n.rear
}
p := n.prefix
n.prefix = p.prefix
p.prefix.rear = n
return p.val
}
/* 依次对双向链表的每个元素调用visit().一旦visit()失败,则栈操作失败*/
func (L *DuLNode) StackTraverse(visitfunc(a ...interface{})) {
if L.prefix == nil {
return
}
n := L
for n != L {
visit(n)
n = n.prefix
}
}
```
网友评论