链表.jpg

链表-存储原理.jpg

链表操作.jpg

链表操作1.jpg

链表操作2.jpg

链表优缺点.jpg

代码示例

package main

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

// Node 节点
type Node struct {
    data int   // data 节点存储数据
    next *Node // next node 下一个节点
}

// SingletonNode 单向链表
type SingleLinkedList struct {
    head *Node // head 头节点
    size int   // size 链表数量
}

// New 创建单向链表
func New() *SingleLinkedList {
    return &SingleLinkedList{}
}

// GetHead 获得头节点
func (l *SingleLinkedList) GetHead() (error, int) {
    if l.IsEmpty() {
        return errors.New("empty list"), 0
    }

    return nil, l.head.data
}

// GetNode 获得节点
// 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 插入节点
// index 索引位置，插入索引之后
// data 插入内容
func (l *SingleLinkedList) AddNode(index, data int) error {
    if l.IsEmpty() {
        // 链表为空，添加头节点
        return l.AddHead(data)
    } else if l.size == index {
        // 添加尾节点
        return l.AddTail(data)
    } else {
        // 找到需要插入节点
        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 添加头节点
func (l *SingleLinkedList) AddHead(data int) error {
    if l.head != nil {
        return errors.New("头节点已经存在")
    }

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

    l.size = 1
    return nil
}

// AddTail 添加尾节点
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 设置节点值
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 获得节点
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 删除节点
func (l *SingleLinkedList) del(index int) error {
    if l.isHead(index) {
        // 头节点
        err, node := l.Node(index)
        if err != nil {
            return err
        }

        node.next = nil
        return nil
    }

    if l.isTail(index) {
        // 尾节点
        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() {
    // 添加节点测试
    // addNodeTest()

    // 超范围测试
    // outSpaceTest()

    // 删除节点
    delNodeTest()
}

func addNodeTest() {
    sll := New()
    // 添加头节点
    sll.AddHead(0)
    // 插入节点
    sll.AddNode(1, 1)
    sll.AddNode(2, 2)
    sll.AddNode(3, 3)
    s := sll.ToString()
    fmt.Println("toString:", s)
}

func outSpaceTest() {
    sll := New()
    // 添加头节点
    sll.AddHead(0)
    err := sll.AddNode(9, 9)
    if err != nil {
        fmt.Println(err)
    }
}

func delNodeTest() {
    sll := New()
    // 添加头节点
    sll.AddHead(0)
    // 插入节点
    sll.AddNode(1, 1)
    sll.AddNode(2, 2)
    sll.AddNode(3, 3)

    sll.del(1)

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