鏈表（Linked List）

什么是鏈表？

通過指針或者引用將一系列數據節(jié)點串起來的數據結構稱為鏈表，鏈表數據結構與數組最明顯的區(qū)別就是它在內存中并不是連續(xù)的，鏈表是通過在每個數據節(jié)點中設置下一個節(jié)點的指針Next將下一個節(jié)點串起來

為什么會有鏈表？

每一個編程語言中都會有數組的數據結構，可以直接通過索引下標來訪問數組中的數據，所以對于數組來說訪問一個值的時間復雜度為O(1)。但是如果要在數組中插入一個值時會有哪些情況呢

1、需要在數組的頭插入
對于這種情況需要將數組中所有的元素往后挪動一步，然后再將待插入的數據插入第一個空間
2、需要在數組中間插入
其實這種情況跟第一種情況是一樣的，只不過往后挪動的數據不是所有數據，只需要挪動待插入節(jié)點后面的數據
3、在數組的后面插入
這種情況最簡單，只需要將待插入節(jié)點插入的最后即可

所以可以看到數組這種數據結構查詢效率是非常高的，但是插入的效率并不高（數組元素的刪除也是一樣的，只不過挪動元素時是向前挪動而已）；因為數組需要在內存中連續(xù)存儲，所以如果插入時數組的空間不夠時還需要動態(tài)擴容就更麻煩了；這時候我們的鏈表就閃亮登場了

什么情況下使用鏈表？

從前面可以看到數組的查詢效率非常高效，但是插入跟刪除時效率并不高；所以為了解決數組的插入和刪除的效率低下就可以使用鏈表
所以如果你的數據是讀多寫少就選擇用數組，相反如果你的數據需要大量的插入和刪除，讀的情況相對較少就可以使用鏈表來存儲你的數據

下面是通過golang語言實現的常見鏈表的面試題
1、單鏈表反轉
2、單鏈表相鄰節(jié)點兩兩反轉
3、檢測鏈表是否有環(huán)
4、獲取鏈表的中間節(jié)點
5、刪除鏈表倒數第N個節(jié)點
6、合并兩個有序鏈表
7、用鏈表實現LRU淘汰算法（最近最少使用淘汰算法）

package linkedlist

import (
    "fmt"
    "sync"
)

type Node struct {
    Value float64 // 這里的類型可以根據業(yè)務決定，我這里為了做有序鏈表合并定義了float64
    Next *Node
}

func (n* Node) String()string{
    if n == nil {
        return ""
    }

    ret := ""
    current := n
    for   {
        if current  == nil{
            ret += fmt.Sprint("nil")
            return ret
        }

        ret += fmt.Sprintf("%v->",current.Value)
        current = current.Next
    }
}

func NewNode(value float64)*Node{
    return &Node{
        Value:value,
    }
}

func NewNodeWithNext(value float64,next * Node)*Node  {
    return &Node{
        Value:value,
        Next:next,
    }
}

// 單鏈表反轉
// input 1->2->3->4
// output 4->3->2->1
/**
 * 思路：pre：指向已經反轉好的節(jié)點的頭結點；current：指向下一個待轉換的結點
 *
 * pre = nil, cur = 1->2->3->4->5->nil
 * pre = 1->nil, cur = 2->3->4->5->nil
 * pre = 2->1->nil, cur = 3->4->5->nil
 * pre = 3->2->1->nil, cur = 4->5->nil
 * ......
 * pre = 5->4->3->2->1->nil, cur = nil
 */
func Traverse(head * Node)*Node  {
    var  pre ,current *Node = nil,head
    for{
        if current == nil{
            return pre
        }
        current.Next,pre,current =pre,current,current.Next
    }
}

// 單鏈表相鄰兩個節(jié)點兩兩反轉
// input 1->2->3->4->5
// output 2->1->4->3->5
/**
 * 思路：如果小于等于一個節(jié)點直接返回不需要反轉
 *      這里必須要標記當前轉換的兩個節(jié)點的前一個節(jié)點，所以在剛開始時必須要構造這么一個節(jié)點
 *
 * pre = 2, cur = 0->1->2->3->4->5
 * pre = 2, cur = 0->2->1->3->4->5
 * pre = 2, cur = 0->2->1->4->3->5
 */
func Traverse2(head * Node)*Node{
    if head == nil || head.Next == nil {
        return head
    }

    pre := head.Next
    cur := NewNodeWithNext(0,head)
    for  {
        if cur.Next == nil || cur.Next.Next == nil{
            return pre
        }

        a := cur.Next
        b := cur.Next.Next
        cur.Next,a.Next,b.Next=b, b.Next,a
        cur = a
    }
}

// 檢測鏈表是否有環(huán)（快慢指針）
func HasCircle(head * Node)bool{
    if head == nil{
        return false
    }

    slow,fast := head,head
    for   {
        if fast.Next == nil || fast.Next.Next == nil || slow.Next == nil {
            return false
        }

        fast = fast.Next.Next
        slow = slow.Next
        if slow == fast{
            return true
        }
    }
}

// 獲取鏈表的中間節(jié)點
func GetMiddleNode(head * Node)* Node{
    if head == nil || head.Next == nil{
        return head
    }

    slow,fast := head,head
    for   {
        if fast.Next != nil && fast.Next.Next != nil && slow.Next != nil {
            slow = slow.Next
            fast=fast.Next.Next
            continue
        }

        return slow
    }
}

// 刪除倒數第n個結點，如果倒數n個結點為頭結點則不可刪除
func RDelNode(head* Node,n int) * Node {
    slow,fast := head,head

    // 1 2 3 4 5
    for ; n > 0 ; n --   {
        if fast.Next == nil {
            break
        }
        fast = fast.Next
    }

    // 如果這里 n == 1 則表示刪除頭結點，目前可以考慮不刪除頭結點
    if n > 0 {
        return nil
    }

    for  {
        if fast.Next != nil && slow.Next != nil {
            fast = fast.Next
            slow = slow.Next
            continue
        }
        break
    }

    if slow != nil && slow.Next != nil{
        ret := slow.Next
        slow.Next = slow.Next.Next
        return ret
    }
    return nil
}

// 合并兩個有序鏈表
/**
 * 思路：因為是有序的鏈表，所以有兩種方式可以做
 * 1、重新開啟一個鏈表，然后從兩個待合并的鏈表的頭中拿下來一個比較小的，放入新的鏈表中直到兩個鏈表都為空
 * 2、上一個方式理解起來比較簡單，但是會額外浪費m+n的空間；所以第二種方式就是一個開頭較大的鏈表插入到開頭較小的鏈表中即可
 */
func Merge(head1,head2 * Node)*Node{
    if head1 == nil{
        return head2
    }

    if head2 == nil{
        return head1
    }

    head,insert := head1,head2
    if head2.Value < head1.Value {
        head,insert = head2,head1
    }

    cur := head
    for {
        if insert == nil{
            return head
        }

        if cur.Next == nil {
            cur.Next = insert
            return head
        }

        for {
            if  insert.Value > cur.Value && cur.Next != nil && insert.Value < cur.Next.Value  {
                tmp := insert.Next
                insert.Next = cur.Next
                cur.Next = insert

                cur = cur.Next
                insert =tmp
                break
            }

            if cur.Next == nil {
                break
            }
            cur = cur.Next
        }
    }
}

// ------------------------**鏈表實現LRU淘汰算法（Least Recently Used）**------------------------------------
/**
 *  思路：
 * 1、如果當前數據在鏈表中存在則將當前數據提到鏈表頭部
 * 2、如果在當前鏈表中不存在
 *  2.1、當前鏈表是否已滿，當前數據替換鏈表中的最后一個節(jié)點
 *  2.2、當前鏈表沒有滿，將當前數據插入到鏈表的頭部
 */
type LeastRecentlyUsed struct {
    Capacity uint64 // 容量
    Number uint64 // 當前鏈表數量
    Head  * Node // 鏈表頭節(jié)點
    mu sync.RWMutex
}

func NewLeastRecentlyUsed(capacity uint64)*LeastRecentlyUsed{
    return &LeastRecentlyUsed{
        Capacity:capacity,
    }
}

// 返回要查找的結點的前一個節(jié)點跟自己的節(jié)點，如果pre為空則要查找的結點就是頭結點
func (l * LeastRecentlyUsed)Find(value interface{})(pre,cur *Node,exist bool){
    l.mu.RLock()
    defer l.mu.RUnlock()

    if l.Head == nil {
        return
    }

    if l.Head.Value == value {
        cur = l.Head
        exist = true
        return
    }

    pre = l.Head
    for  {
        if pre.Next == nil {
            return
        }

        if pre.Next.Value == value {
            cur = pre.Next
            exist = true
            return
        }

        pre = pre.Next
    }
}

func (l * LeastRecentlyUsed)Use(value float64)  {
    pre,cur ,ok := l.Find(value)
    l.mu.Lock()

    // 如果當前節(jié)點已經存在則將當前節(jié)點放在第一個節(jié)點
    if ok && pre != nil{
        pre.Next= cur.Next
        cur.Next = l.Head
        l.Head = cur
        l.mu.Unlock()
        return
    }

    // 如果當前的緩存容量已經滿了，則將當前節(jié)點覆蓋最后一個節(jié)點
    if l.Capacity <= l.Number {
        if l.Capacity <= 1 {
            l.Head = NewNode(value)
            l.mu.Unlock()
            return
        }

        pre := l.Head
        for  {
            if pre.Next.Next != nil {
                pre = pre.Next
                continue
            }

            pre.Next = NewNode(value)
            l.mu.Unlock()
            return
        }

    }else{
        l.Number ++
        newNode := NewNodeWithNext(value,l.Head)
        l.Head = newNode
        l.mu.Unlock()
        return
    }
}

github地址：https://github.com/LiYanBing/golang-data-struct/tree/master/linkedlist

最后編輯于 ：
?著作權歸作者所有,轉載或內容合作請聯系作者
【社區(qū)內容提示】社區(qū)部分內容疑似由AI輔助生成，瀏覽時請結合常識與多方信息審慎甄別。
平臺聲明：文章內容（如有圖片或視頻亦包括在內）由作者上傳并發(fā)布，文章內容僅代表作者本人觀點，簡書系信息發(fā)布平臺，僅提供信息存儲服務。

相關閱讀更多精彩內容

  • 鏈表(Linked-list) 前面我們討論了如何使用棧、隊列進行存數數據，他們其實都是列表的一種，底層存儲的數據...
    Cryptic閱讀 39,343評論 7贊 57
  • 鏈表(Linked-list) 前面我們討論了如何使用棧、隊列進行存數數據，他們其實都是列表的一種，底層存儲的數據...
    yixuan_liu閱讀 250評論 0贊 0
  • 一、什么是鏈表 鏈表跟數組類似，也是一個有序集合。但他們的區(qū)別在于，創(chuàng)建數組時需要分配一大塊內存用來存儲元素，而鏈...
    ShannonChenCHN閱讀 4,518評論 0贊 1
  • 數據結構 - 鏈表 鏈表(linked list)：由一組被稱為結點(也叫節(jié)點)的數據元素組成的數據結構，每個結點...
    惑也閱讀 6,234評論 0贊 3
  • 夏天的清晨靜謐安詳 樹木花草努力的生長 我喜歡獨自一 人 徜徉在家鄉(xiāng)的小路上 聽小鳥喃喃細語 看蝴蝶翩翩起舞 聽花...
    綠瓔珞閱讀 461評論 8贊 11

友情鏈接更多精彩內容