有些人面試時會被問到數(shù)組和鏈表的區(qū)別？試想一下骚腥，你知道嗎

數(shù)組

一種線性表數(shù)據(jù)結構束铭。它用一組連續(xù)的內存空間契沫，來存儲一組具有相同類型的數(shù)據(jù)。最大的特點就是支持隨機訪問会通，但插入涕侈、刪除操作也因此變得比較低效，平均情況時間復雜度為 O(n)调违。在平時的業(yè)務開發(fā)中技肩，我們可以直接使用編程語言提供的容器類，但是然痊，如果是特別底層的開發(fā)剧浸，直接使用數(shù)組可能會更合適唆香。

這個定義里有幾個關鍵詞躬它，理解了這幾個關鍵詞，我想你就能徹底掌握數(shù)組的概念了

• 線性表

顧名思義桑谍，線性表就是數(shù)據(jù)排成像一條線一樣的結構祸挪。每個線性表上的數(shù)據(jù)最多只有前和后兩個方向雹仿。其實除了數(shù)組峻仇，鏈表摄咆、隊列吭从、棧等也是線性表結構。

image.png

而與它相對立的概念是非線性表步做，比如二叉樹、堆讼载、圖等。之所以叫非線性一喘，是因為，在非線性表中闷沥，數(shù)據(jù)之間并不是簡單的前后關系蚂维。

image.png

• 連續(xù)的內存空間和相同類型的數(shù)據(jù)

正是因為這兩個限制蔚约，它才有了一個堪稱“殺手锏”的特性：“隨機訪問”涂籽。但有利就有弊苹祟，這兩個限制也讓數(shù)組的很多操作變得非常低效，比如要想在數(shù)組中刪除评雌、插入一個數(shù)據(jù)树枫，為了保證連續(xù)性，就需要做大量的數(shù)據(jù)搬移工作景东。

鏈表

它并不需要一塊連續(xù)的內存空間团赏，它通過“指針”將一組零散的內存，空間可擴容耐薯，比較常用的是單鏈表曲初，雙鏈表和循環(huán)鏈表。和數(shù)組相比，鏈表更適合插入、刪除操作頻繁的場景吓懈，查詢的時間復雜度較高。不過庆揪，在具體軟件開發(fā)中钧排，要對數(shù)組和鏈表的各種性能進行對比，綜合來選擇使用兩者中的哪一個槽惫。

image.png

• 單鏈表
  1）每個節(jié)點只包含一個指針得糜，即后繼指針。
  2）單鏈表有兩個特殊的節(jié)點，即首節(jié)點和尾節(jié)點打掘。為什么特殊？用首節(jié)點地址表示整條鏈表衙传，尾節(jié)點的后繼指針指向空地址null亭引。
  3）性能特點：插入和刪除節(jié)點的時間復雜度為O（1），查找的時間復雜度為O(n)比庄。

image.png

• 雙鏈表
  1）節(jié)點除了存儲數(shù)據(jù)外强挫，還有兩個指針分別指向前一個節(jié)點地址（前驅指針prev）和下一個節(jié)點地址（后繼指針next）。
  2）首節(jié)點的前驅指針prev和尾節(jié)點的后繼指針均指向空地址趴酣。
  3）性能特點：
  和單鏈表相比抡四，存儲相同的數(shù)據(jù)，需要消耗更多的存儲空間便斥。
  插入跟狱、刪除操作比單鏈表效率更高O(1)級別。以刪除操作為例星立，刪除操作分為2種情況：給定數(shù)據(jù)值刪除對應節(jié)點和給定節(jié)點地址刪除節(jié)點爽茴。對于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進行遍歷從而找到對應節(jié)點進行刪除绰垂，時間復雜度為O(n)室奏。對于第二種情況，要進行刪除操作必須找到前驅節(jié)點劲装，單鏈表需要從頭到尾進行遍歷直到p->next = q胧沫，時間復雜度為O(n)，而雙向鏈表可以直接找到前驅節(jié)點占业，時間復雜度為O(1)绒怨。
  對于一個有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些纺酸。因為我們可以記錄上次查找的位置p窖逗，每一次查詢時址否，根據(jù)要查找的值與p的大小關系餐蔬，決定是往前還是往后查找，所以平均只需要查找一半的數(shù)據(jù)佑附。

  
  
  image.png

• 循環(huán)鏈表
  1）除了尾節(jié)點的后繼指針指向首節(jié)點的地址外均與單鏈表一致樊诺。
  2）適用于存儲有循環(huán)特點的數(shù)據(jù)，比如約瑟夫問題音同。

  
  
  image.png

下面附一個雙鏈表的例子

#import <Foundation/Foundation.h>

@interface Note : NSObject

//上個節(jié)點
@property (nonatomic ,strong) Note *previous;

//下個節(jié)點
@property (nonatomic ,strong) Note *next;

//當前節(jié)點內容
@property (strong , nonatomic) id content;

@end



@interface LinkedList : NSObject

//鏈表長度
@property (assign , nonatomic) NSUInteger size;

//添加節(jié)點
- (void)addObject:(NSObject *)obj;

//插入某節(jié)點前
- (void)insertObject:(NSObject *)obj nextObject:(NSObject *)nextObj;

//移除指定節(jié)點
- (void)remove:(NSObject *)obj;

//移除指定索引節(jié)點
- (void)removeAtIndex:(NSInteger)index;

//獲取指定位置的值
- (NSObject *)objectAtIndex:(NSInteger)index;

//鏈表初始化
+ (instancetype)list;

@end

@implementation Note

@end

#import "LinkedList.h"
#import "Note.h"

@interface LinkedList ()

//首個節(jié)點
@property (nonatomic, strong) Note *first;

//最后節(jié)點
@property (nonatomic, strong) Note *last;

@end

@implementation LinkedList

- (void)addObject:(NSObject *)obj
{
    if (!obj) return;
    self.size++;
    
    Note *note = [[Note alloc] init];

    if (!self.first)
    {
        self.first = note;
        self.last = note;
        
        note.previous = nil;
        note.next = nil;
        note.content = obj;
        
        return;
    }
    
    //新節(jié)點
    note.previous = self.last;
    note.next = nil;
    note.content = obj;
    
    //給上一個節(jié)點next賦值
    self.last.next = note;
    
    //給first.next賦值
    if (!self.first.next)
    {
        self.first.next = note;
    }

    self.last = note;
}

- (void)insertObject:(NSObject *)obj nextObject:(NSObject *)nextObj
{
    if (!obj || !nextObj || !self.size) return;
    
    Note *tempNote = self.first;
    
    for (NSInteger index = 0; index < self.size; index++)
    {
        if ([tempNote.content isEqual:nextObj])
        {
            break;
        }
        tempNote = tempNote.next;
    }
    
    Note *nextNote = tempNote.next;
    
    Note *note = [[Note alloc] init];
    note.previous = tempNote;
    note.next = nextNote;
    note.content = obj;
    
    tempNote.next = note;
    nextNote.previous = note;
}

- (void)remove:(NSObject *)obj
{
    if (!obj || !self.size) return;
    
    Note *tempNote = self.first;
    
    for (NSInteger index = 0; index < self.size; index++)
    {
        if ([tempNote.content isEqual:obj])
        {
            [self removeNote:tempNote]; //移除節(jié)點
            
            break;
        }
        tempNote = tempNote.next;
    }
}


//根據(jù)索引移除元素
- (void)removeAtIndex:(NSInteger)index
{
    if (index < 0 || index >= self.size) return;
    
    Note *tempNote = self.first;
    
    for (NSInteger i = 0; i < self.size; i ++)
    {
        if (i == index)
        {
            [self removeNote:tempNote]; //移除節(jié)點
            break;
        }
        tempNote = tempNote.next;
    }
}

- (void)removeNote:(Note *)note
{
    //連接上下節(jié)點
    Note *preNote     = note.previous;
    Note *nextNote    = note.next;
    preNote.next      = nextNote;
    nextNote.previous = preNote;
    note.content      = nil; //清空被移除節(jié)點內容
    self.size--;//長度更新
}


//獲取指定索引元素
- (NSObject *)objectAtIndex:(NSInteger)index
{
    if (index<0 || index >= self.size) return nil;
    
    Note *tempNote = self.first;
    
    for (NSInteger i = 0; i < self.size; i++)
    {
        if (i == index)
        {
            return tempNote.content;
        }
        tempNote = tempNote.next;
    }
    
    return nil;
}

//構造方法
+ (instancetype)list
{
    return [[self alloc] init];
}

@end

單鏈表反轉和鏈表中環(huán)的檢測是面試里面經常涉及到的考點词爬，下面是具體實例

單鏈表反轉（迭代方式）

迭代的方式是從鏈頭開始處理，如下圖給定一個存放5個數(shù)的鏈表权均。

image.png

首先對于鏈表設置兩個指針：

image.png

然后依次將舊鏈表上每一項添加在新鏈表的后面顿膨，然后新鏈表的頭指針NewH移向新的鏈表頭锅锨，如下圖所示。此處需要注意恋沃，不可以上來立即將上圖中P->next直接指向NewH必搞，這樣存放2的地址就會被丟棄，后續(xù)鏈表保存的數(shù)據(jù)也隨之無法訪問囊咏。而是應該設置一個臨時指針tmp恕洲，先暫時指向P->next指向的地址空間，保存原鏈表后續(xù)數(shù)據(jù)梅割。然后再讓P->next指向NewH霜第，最后P=tmp就可以取回原鏈表的數(shù)據(jù)了，所有循環(huán)訪問也可以繼續(xù)展開下去户辞。

image.png

指針繼續(xù)向后移動泌类，直到P指針指向NULL停止迭代。

image.png

最后一步：

image.png

- (Node *)reverseList:(Node *)headNode
{
    //鏈表為空或者僅1個數(shù)直接返回
    if (headNode == nil || headNode.next == nil)
    {
        return headNode;
    }
    
    Node *p = headNode;
    Node *newHead = nil;
    
    //一直迭代到鏈尾
    while (p != nil)
    {
        //暫存p下一個地址咆课，防止變化指針指向后找不到后續(xù)的數(shù)
        Node *tempNode = p.next;
        
        //p->next指向前一個空間
        p.next = newHead;
        
        //新鏈表的頭移動到p末誓，擴長一步鏈表
        newHead = p;
        
        //p指向原始鏈表p指向的下一個空間
        p = tempNode;
    }
    
    return newHead;
}

單鏈表反轉（遞歸方式）

首先指針H迭代到底如下圖所示，并且設置一個新的指針作為翻轉后的鏈表的頭书蚪。由于整個鏈表翻轉之后的頭就是最后一個數(shù)喇澡，所以整個過程NewH指針一直指向存放5的地址空間。

image.png

然后H指針逐層返回的時候依次做下圖的處理殊校，將H指向的地址賦值給H->next->next指針晴玖，并且一定要記得讓H->next =NULL，也就是斷開現(xiàn)在指針的鏈接为流，否則新的鏈表形成了環(huán)呕屎，下一層H->next->next賦值的時候會覆蓋后續(xù)的值。

image.png

繼續(xù)返回操作：

image.png

上圖第一次如果沒有將存放4空間的next指針賦值指向NULL敬察，第二次H->next->next=H秀睛，就會將存放5的地址空間覆蓋為3，這樣鏈表一切都大亂了莲祸。接著逐層返回下去蹂安，直到對存放1的地址空間處理。

image.png

返回到頭：

image.png

- (Node *)reverseSingleList:(Node *)headNode
{
    //鏈表為空直接返回锐帜，而H->next為空是遞歸基
    if (headNode == nil || headNode.next == nil)
    {
        return headNode;
    }
    
    //一直循環(huán)到鏈尾
    Node *newHead = [self reverseSingleList:headNode.next];
    
    //翻轉鏈表的指向
    headNode.next.next = headNode;
    
    //記得賦值NULL田盈，防止鏈表錯亂
    headNode.next = nil;
    
    //新鏈表頭永遠指向的是原鏈表的鏈尾
    return newHead;
}

鏈表中環(huán)的檢測

• 首先設置兩個指針，分別命名為fast和slow缴阎，fast指針每次向后移2步允瞧，slow指針每次向后移1步。
• 如果，fast指針最后走到尾結點述暂，則沒有環(huán)痹升。
• 如果，fast指針和slow指針相遇畦韭，則證明有環(huán)视卢。

SingleList *single = [SingleList new];
    
    Node *nodeOne = [Node new];
    nodeOne.content = @"1";
    
    single.first = nodeOne;
    
    Node *nodeTwo = [Node new];
    nodeTwo.content = @"2";
    nodeOne.next = nodeTwo;
    
    Node *nodeThree = [Node new];
    nodeThree.content = @"3";
    nodeTwo.next = nodeThree;
    
    Node *nodeFour = [Node new];
    nodeFour.content = @"4";
    nodeThree.next = nodeFour;

    Node *nodeFive = [Node new];
    nodeFive.content = @"5";
    nodeFour.next = nodeFive;

    Node *nodeSix = [Node new];
    nodeSix.content = @"6";
    nodeFive.next = nodeSix;

    Node *nodeSeven = [Node new];
    nodeSeven.content = @"7";
    nodeSix.next = nodeSeven;

    Node *nodeEight = [Node new];
    nodeEight.content = @"8";
    nodeSeven.next = nodeEight;
    nodeEight.next = nodeFive;
    
    single.last = nodeEight;
    
    Node *fast = single.first.next;
    Node *slow = single.first;
    
    BOOL isFind;
    
    while (![fast isEqual:slow] && fast)
    {
        fast = fast.next.next;
        slow = slow.next;
        
        if (fast == nil)
        {
            isFind = NO;
        }

        if (fast == slow)
        {
            isFind = YES;
        }
    }

最后總結兩者區(qū)別

先看時間復雜度上的區(qū)別

image.png

不過，數(shù)組和鏈表的對比廊驼，并不能局限于時間復雜度据过。而且，在實際的軟件開發(fā)中妒挎，不能僅僅利用復雜度分析就決定使用哪個數(shù)據(jù)結構來存儲數(shù)據(jù)绳锅。

數(shù)組簡單易用，在實現(xiàn)上使用連續(xù)的內存空間酝掩，可以借助CPU的緩沖機制預讀數(shù)組中的數(shù)據(jù)鳞芙，所以訪問效率更高，而鏈表在內存中并不是連續(xù)存儲期虾，所以對CPU緩存不友好原朝，沒辦法預讀。

數(shù)組的缺點是大小固定镶苞，一經聲明就要占用整塊連續(xù)內存空間喳坠。如果聲明的數(shù)組過大，系統(tǒng)可能沒有足夠的連續(xù)內存空間分配給它茂蚓，導致“內存不足（out of memory）”壕鹉。如果聲明的數(shù)組過小，則可能出現(xiàn)不夠用的情況聋涨。這時只能再申請一個更大的內存空間晾浴，把原數(shù)組拷貝進去，非常費時牍白。鏈表本身沒有大小的限制脊凰，天然地支持動態(tài)擴容，我覺得這也是它與數(shù)組最大的區(qū)別茂腥。

如果代碼對內存的使用非忱暧浚苛刻，那數(shù)組就更適合础芍。因為鏈表中的每個結點都需要消耗額外的存儲空間去存儲一份指向下一個結點的指針杈抢，所以內存消耗會翻倍数尿。而且仑性，對鏈表進行頻繁的內存申請和釋放，容易造成內存碎片右蹦，如果是 Java 語言诊杆，就有可能會導致頻繁的 GC（Garbage Collection歼捐，垃圾回收）。