鏈表.jpg

鏈表-存儲原理.jpg

鏈表操作.jpg

鏈表操作1.jpg

鏈表操作2.jpg

鏈表優(yōu)缺點.jpg

代碼示例

package main

import (
    "errors"
    "fmt"
    "strconv"
)

// Node 節(jié)點
type Node struct {
    data int   // data 節(jié)點存儲數(shù)據(jù)
    next *Node // next node 下一個節(jié)點
}

// SingletonNode 單向鏈表
type SingleLinkedList struct {
    head *Node // head 頭節(jié)點
    size int   // size 鏈表數(shù)量
}

// New 創(chuàng)建單向鏈表
func New() *SingleLinkedList {
    return &SingleLinkedList{}
}

// GetHead 獲得頭節(jié)點
func (l *SingleLinkedList) GetHead() (error, int) {
    if l.IsEmpty() {
        return errors.New("empty list"), 0
    }

    return nil, l.head.data
}

// GetNode 獲得節(jié)點
// index 鏈表索引
func (l *SingleLinkedList) GetNode(index int) (error, int) {
    err, node := l.Node(index)

    if err != nil {
        return err, 0
    }

    return nil, node.data
}

// AddNode 插入節(jié)點
// index 索引位置岭妖，插入索引之后
// data 插入內(nèi)容
func (l *SingleLinkedList) AddNode(index, data int) error {
    if l.IsEmpty() {
        // 鏈表為空掀宋，添加頭節(jié)點
        return l.AddHead(data)
    } else if l.size == index {
        // 添加尾節(jié)點
        return l.AddTail(data)
    } else {
        // 找到需要插入節(jié)點
        err, node := l.Node(index)

        if err != nil {
            return err
        }

        newNode := &Node{
            data: data,
            next: node.next,
        }

        node.next = newNode

        l.size = l.size + 1
        return nil
    }
}

// AddHead 添加頭節(jié)點
func (l *SingleLinkedList) AddHead(data int) error {
    if l.head != nil {
        return errors.New("頭節(jié)點已經(jīng)存在")
    }

    l.head = &Node{
        data: data,
        next: nil,
    }

    l.size = 1
    return nil
}

// AddTail 添加尾節(jié)點
func (l *SingleLinkedList) AddTail(data int) error {
    err, tail := l.Node(l.size - 1)
    if err != nil {
        return err
    }

    newTail := &Node{
        data: data,
        next: nil,
    }

    tail.next = newTail
    l.size = l.size + 1

    return nil
}

// SetNode 設(shè)置節(jié)點值
func (l *SingleLinkedList) SetNode(index, data int) error {
    err, node := l.Node(index)
    if err != nil {
        return err
    } else {
        node.data = data
        return nil
    }
}

// IsEmpty 鏈表是否為空
func (l *SingleLinkedList) IsEmpty() bool {
    return l.size == 0
}

// node 獲得節(jié)點
func (l *SingleLinkedList) Node(index int) (error, *Node) {
    if l.IsEmpty() {
        return errors.New("empty list"), nil
    }

    if l.isOutSpace(index) {
        return errors.New("下標無效每强，越界疆虚。"), nil
    }

    //  TODO 二分查找

    node := l.head

    for i := 0; i < index; i++ {
        node = node.next
    }

    return nil, node
}

// isOutSpace 是否超出范圍
func (l *SingleLinkedList) isOutSpace(index int) bool {
    if l.size < index || index < 0 {
        // 越界
        return true
    }
    return false
}

func (l *SingleLinkedList) isHead(index int) bool {
    return index == 0
}

func (l *SingleLinkedList) isTail(index int) bool {
    return index == l.size-1
}

// del 刪除節(jié)點
func (l *SingleLinkedList) del(index int) error {
    if l.isHead(index) {
        // 頭節(jié)點
        err, node := l.Node(index)
        if err != nil {
            return err
        }

        node.next = nil
        return nil
    }

    if l.isTail(index) {
        // 尾節(jié)點
        err, node := l.Node(index - 1)
        if err != nil {
            return err
        }

        node.next = nil
        return nil
    }

    err, prev := l.Node(index - 1)
    if err != nil {
        return err
    }
    err, next := l.Node(index + 1)
    if err != nil {
        return err
    }

    prev.next = next

    return nil
}

// ToString
func (l *SingleLinkedList) ToString() string {
    var str = ""
    node := l.head
    var s = strconv.Itoa(node.data)
    str += s + ","

    for i := 0; i < l.size; i++ {
        if node.next != nil {
            node = node.next
            var s = strconv.Itoa(node.data)
            str += s + ","
        }
    }

    return str
}

func main() {
    // 添加節(jié)點測試
    // addNodeTest()

    // 超范圍測試
    // outSpaceTest()

    // 刪除節(jié)點
    delNodeTest()
}

func addNodeTest() {
    sll := New()
    // 添加頭節(jié)點
    sll.AddHead(0)
    // 插入節(jié)點
    sll.AddNode(1, 1)
    sll.AddNode(2, 2)
    sll.AddNode(3, 3)
    s := sll.ToString()
    fmt.Println("toString:", s)
}

func outSpaceTest() {
    sll := New()
    // 添加頭節(jié)點
    sll.AddHead(0)
    err := sll.AddNode(9, 9)
    if err != nil {
        fmt.Println(err)
    }
}

func delNodeTest() {
    sll := New()
    // 添加頭節(jié)點
    sll.AddHead(0)
    // 插入節(jié)點
    sll.AddNode(1, 1)
    sll.AddNode(2, 2)
    sll.AddNode(3, 3)

    sll.del(1)

    s := sll.ToString()
    fmt.Println("toString:", s)
}