链表（Linked list）是一种 “动态数据结构”，链表由节点构成node链接构成，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的指针。
相比数组，数组的内存地址是连续的，而链表不用连续的内存地址
链表是动态数据结构，用链表组成的栈和队列数据结构，不用做扩容和缩容操作
node 节点一般存储两个元素，本节点内容content和下一个节点指针next，结构如下
type Node struct{
Content interface{}
Next *Node
}
链表由节点组成，由3个元素组成，length链表长度，head头节点，tail尾节点，结构如下
type LinkedList struct{
Length int
Head *Node
Tail *Node
}
// 单链表数据结构的实现
// 节点
type node struct {
Item interface{}
Next *node
}
// 链表
type linkedList struct {
Length int
DummyHead *node //虚拟头节点，可以统一头节点和其他节点的操作，达到简化逻辑的效果
}
func NewNode() *node {
return &node{
Item: nil,
Next: nil,
}
}
func NewLinkedList() *linkedList {
return &linkedList{
Length: 0,
DummyHead: &node{},
}
}
func (l *linkedList) Add(index int, n *node) {
if index < 0 || index > l.Length {
log.Fatal("failed to add, index 超出范围.")
}
prev := l.DummyHead
for i := 0; i < index; i++ {
prev = prev.Next
}
n.Next = prev.Next
prev.Next = n
l.Length++
}
func (l *linkedList) AddFirst(n *node) {
l.Add(0, n)
}
func (l *linkedList) AddLast(n *node) {
l.Add(l.Length-1, n)
}
// 输入index，返回index位节点
func (l *linkedList) Get(index int) (cur *node, err error) {
if index < 0 || index > l.Length {
err = errors.New("failed to traverse, index out of range.")
return nil, err
}
if l.Length == 0 {
log.Fatal("failed to traverse,linkedList is empty.")
}
cur = l.DummyHead //虚拟头节点
for i := 0; i <= index; i++ {
cur = cur.Next //index位节点
}
return cur, nil
}
// 修改index节点
func (l *linkedList) Modify(index int, n *node) {
if index < 0 || index > l.Length {
log.Fatal("failed to modify, index out of range.")
}
if l.Length == 0 {
log.Fatal("failed to traverse,linkedList is empty.")
}
cur, _ := l.Get(index)
cur.Item = n.Item
cur.Next = n.Next
}
// 修改index节点内容
func (l *linkedList) ModifyContent(index int, item interface{}) {
if index < 0 || index > l.Length {
log.Fatal("failed to modifyContent, index out of range.")
}
if l.Length == 0 {
log.Fatal("failed to traverse,linkedList is empty.")
}
cur, _ := l.Get(index)
cur.Item = item
}
func (l *linkedList) Delete(index int) error {
if index < 0 || index > l.Length {
return errors.New("failed to delete, index out of range.")
}
prev := l.DummyHead
for i := 0; i < index; i++ {
prev = prev.Next
}
delNode := prev.Next
prev.Next = delNode.Next
delNode = nil
l.Length--
return nil
}
// 查找链表中是否有元素e
func (l *linkedList) Contains(n *node) bool {
if l.Length == 0 {
return false
}
cur := l.DummyHead //虚拟头节点
for i := 0; i <= l.Length-1; i++ {
cur = cur.Next //index位节点
if cur == n {
return true
}
}
return false
}
// 获取链表中所有内容
func (l *linkedList) Traverse() []interface{} {
resp := []interface{}{}
buf := l.DummyHead.Next
for buf != nil {
resp = append(resp, buf.Item, "->")
buf = buf.Next
}
resp = append(resp, nil)
return resp
}
// 测试链表
func main() {
l := linked_list1.NewLinkedList()
q := linked_list1.NewNode()
for i := 0; i < 5; i++ {
buf := linked_list1.NewNode()
buf.Item = i
l.AddFirst(buf)
resp := l.Traverse()
fmt.Println(resp)
}
fmt.Println(l.Contains(q))
for i := 0; i < 5; i++ {
l.ModifyContent(i, 8+i)
resp := l.Traverse()
fmt.Println(resp)
}
for i := 0; i < 5; i++ {
l.Delete(4 - i)
resp := l.Traverse()
fmt.Println(resp)
}
l.Modify(1, q)
resp := l.Traverse()
fmt.Println(resp)
}
// 测试结果
[0 -> <nil>]
[1 -> 0 -> <nil>]
[2 -> 1 -> 0 -> <nil>]
[3 -> 2 -> 1 -> 0 -> <nil>]
[4 -> 3 -> 2 -> 1 -> 0 -> <nil>]
false
[8 -> 3 -> 2 -> 1 -> 0 -> <nil>]
[8 -> 9 -> 2 -> 1 -> 0 -> <nil>]
[8 -> 9 -> 10 -> 1 -> 0 -> <nil>]
[8 -> 9 -> 10 -> 11 -> 0 -> <nil>]
[8 -> 9 -> 10 -> 11 -> 12 -> <nil>]
[8 -> 9 -> 10 -> 11 -> <nil>]
[8 -> 9 -> 10 -> <nil>]
[8 -> 9 -> <nil>]
[8 -> <nil>]
[<nil>]
2019/04/16 23:59:31 failed to modify, index out of range.
