鏈表分為單鏈表，雙向鏈表和循環(huán)鏈表

鏈表的時間復(fù)雜度

• 插入 O(n)
• 刪除 O(1)
• 隨機訪問 O(n)

單雙鏈表比較

雙向鏈表優(yōu)于單鏈表的優(yōu)點是 可以在O(1)時間復(fù)雜度的情況下找到前驅(qū)節(jié)點。這樣可以某些情況下快速的插入刪除操作比單鏈表簡單高效。但是空間復(fù)雜度要比單鏈表高

其實時間復(fù)雜度和空間復(fù)雜度，是相輔相成的，以時間換空間 或者以空間換時間。 比如復(fù)雜度O(n)的排序（桶排序 基數(shù)排序等）比快排冒泡排序快就是因為占用了大量的空間，在空間內(nèi)基本上有序，這樣就降低了時間復(fù)雜度。

數(shù)組和鏈表的比較

數(shù)組是連續(xù)的內(nèi)存塊， 一經(jīng)聲明就要占用整塊的內(nèi)存空間， 如果聲明一個很大的數(shù)組， 但是內(nèi)存中沒有那么大的連續(xù)空間則聲明失敗， 但是鏈表則不存在這些問題。

bb這么多，來看go版本的代碼實現(xiàn)（go中有一個庫叫container已經(jīng)實現(xiàn)了鏈表這種數(shù)據(jù)結(jié)果可以拿來直接使用）：

• 完成基本的準(zhǔn)備工作：

// 節(jié)點結(jié)構(gòu)體
type ListNode struct {
    next *ListNode
    value interface{}
}

// 鏈表結(jié)構(gòu)體
type LinkedList struct {
    head *ListNode 
    length uint
}

func NewListNode(v interface{}) *ListNode {
    return &ListNode{nil, v}
}

func (this *ListNode) GetNext() *ListNode {
    return this.next
}

// 獲取節(jié)點值
func (this *ListNode) GetValue() interface{} {
    return this.value
}
// 穿件新的鏈表
func NewLinkedList() *LinkedList {
    return &LinkedList{NewListNode(0), 0}
}

• 鏈表的操作：

// 插入 
func (this *LinkedList) InsertAfter(p *ListNode, v interface{}) bool {
    if nil == p {
        return false
    }
    // 斷開p的next，然后插入新的next 再連接到一起
    newNode := NewListNode(v)
    oldNext := p.GetNext()
    p.next = newNode
    newNode.next = oldNext
    this.length++
    return true
}

// 在某節(jié)點前方插入
func (this *LinkedList) InsertBefore(p *ListNode, v interface{}) bool {
    if nil == p || p == this.head {
        return false
    }
    cur := this.head.next
    pre := this.head
    
    for nil != cur {
        if cur == p {
            break
        }
        pre = cur 
        cur = cur.next
    }
    
    newNode := NewListNode(v)
    pre.next = newNode
    newNode.next = cur 
    this.length++
    return true
}

func (this *LinkedList) InsertToHead(v interface{}) bool {
    return this.InsertAfter(this.head, v)
}

func (this *LinkedList) InsertToTail(v interface{}) bool {
    cur := this.head
    for nil != cur.next {
        cur = cur.next
    }
    return this.InsertAfter(cur, v)
}

• 查找操作

func (this *LinkedList) FindByIndex(index uint) *ListNode{
    if index >= this.length {
        return nil 
    }
    cur := this.head.next
    var i uint = 0
    for ; i<index; i++ {
        cur = cur.next
    }
    return cur
}

• 刪除操作

// 通過操作兩個指針找到對應(yīng)的p然后斷開去掉p再重新連上。
func (this *LinkedList) DeleteNode(p *ListNode) bool {
    if p == nil {
        return false
    }
    cur := this.head.next
    pre := this.head
    for nil != cur {
        if cur == p {
            break
        }
        pre = cur 
        cur = cur.next
    }
    if nil == cur {
        return false
    }
    pre.next = p.next
    p = nil 
    this.length--
    return true 
}

• 打印

func (this *LinkedList) Print() {
    cur := this.head.next
    format := ""
    for nil != cur {
        format += fmt.Sprintf("%+v", cur.GetValue())
        cur = cur.next
        if nil != cur {
            format += "->"
        }
        fmt.Println(format)
    }
}

鏈表的操作基本上實現(xiàn)。
如何讓鏈表能快速的查找， 可以通過鏈表來實現(xiàn)跳表這種類似索引功能的數(shù)據(jù)結(jié)構(gòu)來增加查找速度。但是同樣的是以空間換時間。

判斷是否有環(huán)

func (this *LinkedList) HasCycle() bool {
    // 快慢指針判斷是否有環(huán) 
    if nil != this.head{
        slow := this.head
        fast := this.head.next
        for nil != fast && nil != fast.next {
            slow = slow.next
            fast = fast.next.next
            if slow == fast {
                return true
            }
        }
    }
    return false
}

判斷是否是回文字符串

func isPalindrome(l *LinkedList) bool {
    lLen := l.length
    if lLen == 0 {
        return false
    }
    if lLen == 1 {
        return true
    }

    s := make([]string, 0, lLen/2)
    cur := l.head
    for i := uint(1); i < lLen; i++ {
        // 先把前一半數(shù)據(jù)裝載到數(shù)組 進行比較
        cur = cur.next
        if lLen % 2 != 0 && i == (lLen/2 + 1) {
            continue
        }
        if i <= lLen / 2 {
            s = append(s, cur.GetValue().(string))
        }else {
            if s[lLen - 1] != cur.GetValue().(string) {
                return false
            }
        }
    }
    return true
}