数组与链表

数组

• 数组最大的特点是可以根据下标随机访问，因为它有连续的内存空间
• 缺点是删除和插入要搬移数据
• 下标访问的时间复杂度是O(1)
• 插入和删除操作最坏的时间复杂度是O(N)

链表

• 链表不需要连续的内存空间，通过指针串联不相邻的内存块
• 下标随机访问O(N)
• 插入和删除的时间复杂度是O(1)

单链表的实现

//单链表实现
type SKNode struct {
    Next *SKNode
    Data interface{}
}

func NewSKNode(data interface{}) *SKNode {
    return &SKNode{Data: data}
}

type SKList struct {
    Head *SKNode
    Tail *SKNode
}

func (s *SKList) AppendToTail(d interface{}) {
    end := NewSKNode(d)
    if s.Head == nil {
        s.Head = end
    }
    s.Tail.Next = end
    s.Tail = end
}
func (s *SKList) Delete(d interface{}) {
    h := s.Head
    if h.Data == d {
        s.Head = nil
        s.Tail = nil
        return
    }
    for h.Next != nil {
        if h.Next.Data == d {
            if h.Next == s.Tail {
                s.Tail = h
            }
            h.Next = h.Next.Next
            return
        }
        h = h.Next
    }
}

双链表的实现

type DKNode struct {
    Pre  *DKNode
    Next *DKNode
    Data interface{}
}

func NewDKNode(data interface{}) *DKNode {
    return &DKNode{Data: data}
}

type DKList struct {
    Head *DKNode
    Tail *DKNode
}

func (s *DKList) AppendToTail(d interface{}) {
    n := NewDKNode(d)
    if s.Head == nil {
        s.Head = n
        s.Tail = n
        n.Pre = s.Head
        return
    }
    s.Tail.Next = n
    n.Pre = s.Tail
    s.Tail = s.Tail.Next
}

func (s *DKList) AppendToHead(d interface{}) {
    n := NewDKNode(d)
    if s.Head == nil {
        s.Head = n
        s.Tail = n
        n.Pre = s.Head
        return
    }
    s.Head.Pre = n
    n.Next = s.Head
    s.Head = s.Head.Pre
}

func (s *DKList) Delete(d interface{}) {
    h := s.Head
    if h.Data == d {
        s.Head = nil
        s.Tail = nil
        return
    }
    for h.Next != nil {
        if h.Next.Data == d {
            if h.Next == s.Tail {
                s.Tail = h
            }
            if h.Next.Next != nil {
                h.Next.Next.Pre = h
            }
            h.Next = h.Next.Next
            return
        }
        h = h.Next
    }
}