數(shù)據(jù)結(jié)構(gòu)系列：Objective-C實(shí)現(xiàn)單鏈表

摘自《維基百科》
?
鏈表（Linked list）是一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)焕议。由于不必須按順序存儲(chǔ)逮京，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多嘱根，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間髓废，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是O(logn)和O(1)。
?
使用鏈表結(jié)構(gòu)可以克服數(shù)組鏈表需要預(yù)先知道數(shù)據(jù)大小的缺點(diǎn)该抒，鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間慌洪，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。但是鏈表失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)凑保，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域冈爹，空間開(kāi)銷比較大。
?
在計(jì)算機(jī)科學(xué)中欧引，鏈表作為一種基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)可以用來(lái)生成其它類型的數(shù)據(jù)結(jié)構(gòu)频伤。鏈表通常由一連串節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含任意的實(shí)例數(shù)據(jù)（data fields）和一或兩個(gè)用來(lái)指向上一個(gè)/或下一個(gè)節(jié)點(diǎn)的位置的鏈接（"links"）芝此。鏈表最明顯的好處就是憋肖，常規(guī)數(shù)組排列關(guān)聯(lián)項(xiàng)目的方式可能不同于這些數(shù)據(jù)項(xiàng)目在記憶體或磁盤上順序，數(shù)據(jù)的訪問(wèn)往往要在不同的排列順序中轉(zhuǎn)換婚苹。而鏈表是一種自我指示數(shù)據(jù)類型岸更，因?yàn)樗赶蛄硪粋€(gè)相同類型的數(shù)據(jù)的指針（鏈接）。鏈表允許插入和移除表上任意位置上的節(jié)點(diǎn)膊升，但是不允許隨機(jī)存取坐慰。鏈表有很多種不同的類型：?jiǎn)蜗蜴湵恚p向鏈表以及循環(huán)鏈表。

單向鏈表

摘自《維基百科》
?
鏈表中最簡(jiǎn)單的一種是單向鏈表结胀，它包含兩個(gè)域赞咙，一個(gè)信息域和一個(gè)指針域。這個(gè)鏈接指向列表中的下一個(gè)節(jié)點(diǎn)糟港，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值攀操。
?
一個(gè)單向鏈表的節(jié)點(diǎn)被分成兩個(gè)部分。第一個(gè)部分保存或者顯示關(guān)于節(jié)點(diǎn)的信息秸抚，第二個(gè)部分存儲(chǔ)下一個(gè)節(jié)點(diǎn)的地址速和。單向鏈表只可向一個(gè)方向遍歷。
?
鏈表最基本的結(jié)構(gòu)是在每個(gè)節(jié)點(diǎn)保存數(shù)據(jù)和到下一個(gè)節(jié)點(diǎn)的地址剥汤，在最后一個(gè)節(jié)點(diǎn)保存一個(gè)特殊的結(jié)束標(biāo)記颠放，另外在一個(gè)固定的位置保存指向第一個(gè)節(jié)點(diǎn)的指針，有的時(shí)候也會(huì)同時(shí)儲(chǔ)存指向最后一個(gè)節(jié)點(diǎn)的指針吭敢。一般查找一個(gè)節(jié)點(diǎn)的時(shí)候需要從第一個(gè)節(jié)點(diǎn)開(kāi)始每次訪問(wèn)下一個(gè)節(jié)點(diǎn)碰凶，一直訪問(wèn)到需要的位置。但是也可以提前把一個(gè)節(jié)點(diǎn)的位置另外保存起來(lái)鹿驼，然后直接訪問(wèn)欲低。當(dāng)然如果只是訪問(wèn)數(shù)據(jù)就沒(méi)必要了，不如在鏈表上儲(chǔ)存指向?qū)嶋H數(shù)據(jù)的指針畜晰。這樣一般是為了訪問(wèn)鏈表中的下一個(gè)或者前一個(gè)（需要儲(chǔ)存反向的指針砾莱，見(jiàn)下一篇的雙向鏈表）節(jié)點(diǎn)。
?
這種普通的凄鼻，每個(gè)節(jié)點(diǎn)只有一個(gè)指針的鏈表也叫單向鏈表腊瑟，或者單鏈表，通常用在每次都只會(huì)按順序遍歷這個(gè)鏈表的時(shí)候（例如圖的鄰接表块蚌，通常都是按固定順序訪問(wèn)的）扫步。

單向鏈表的大致情況介紹完畢，以上就是維基百科中對(duì)于單向鏈表的簡(jiǎn)介匈子。接下來(lái)我以最簡(jiǎn)單的形式實(shí)現(xiàn)單向鏈表，鏈表中的節(jié)點(diǎn)儲(chǔ)存最基礎(chǔ)的數(shù)據(jù)類型NSInteger闯袒，便于思考也方便初學(xué)者學(xué)習(xí)虎敦。好了，程序員的世界沒(méi)有BB政敢，直接上源碼其徙！下面就是單向鏈表的核心實(shí)現(xiàn)代碼以及實(shí)例調(diào)用。

@implementation SinglyLinkedList

/**
 初始化一個(gè)單向鏈表
 
 @param node 鏈表的頭節(jié)點(diǎn)
 @return 返回一個(gè)已初始化的單向鏈表
 */
- (instancetype)initWithNode:(SinglyLinkedListNode *)node {
    self = [super init];
    
    if (self) {
        self.headNode = node;
    }
    
    return self;
}

/**
 判斷鏈表是否為空
 
 @return 為空返回YES喷户，反之為NO
 */
- (BOOL)isEmpty {
    return self.headNode == nil;
}

/**
 獲取鏈表?yè)碛械目偣?jié)點(diǎn)數(shù)
 
 @return 總節(jié)點(diǎn)數(shù)
 */
- (NSInteger)length {
    // cur游標(biāo)(指針),用來(lái)移動(dòng)遍歷節(jié)點(diǎn)
    SinglyLinkedListNode *cur = self.headNode;
    
    // count記錄數(shù)量
    NSInteger count = 0;
    
    while (cur) {
        count++;
        cur = cur.nextNode;
    }
    
    return count;
}

/**
 遍歷鏈表
 */
- (void)travel {
    // 空鏈表的情況
    if ([self isEmpty]) return;
    
    SinglyLinkedListNode *cur = self.headNode;
    
    while (cur) {
        NSLog(@"%ld",cur.element);
        cur = cur.nextNode;
    }
}

/**
 頭插法：在鏈表的頭部插入節(jié)點(diǎn)
 
 @param item 插入的元素
 */
- (void)insertNodeAtHeadWithItem:(NSInteger)item {
    SinglyLinkedListNode *node = [[SinglyLinkedListNode alloc] initWithItem: item];
    
    node.nextNode = self.headNode;
    self.headNode = node;
}

/**
 尾插法：在鏈表的尾部插入節(jié)點(diǎn)
 
 @param item 插入的元素
 */
- (void)appendNodeWithItem:(NSInteger)item {
    SinglyLinkedListNode *node = [[SinglyLinkedListNode alloc] initWithItem: item];
    
    if ([self isEmpty]) {
        self.headNode = node;
    }
    else {
        SinglyLinkedListNode *cur = self.headNode;
        
        while (cur.nextNode) {
            cur = cur.nextNode;
        }
        
        cur.nextNode = node;
    }
}

/**
 指定位置插入節(jié)點(diǎn)
 
 @param item 插入的元素
 @param index 位置的索引
 */
- (void)insertNodeWithItem:(NSInteger)item atIndex:(NSInteger)index {
    
    if (index <= 0) {
        [self insertNodeAtHeadWithItem: item];
    }
    else if (index > ([self length] - 1)) {
        [self appendNodeWithItem: item];
    }
    else {
        SinglyLinkedListNode *pre = self.headNode;
        
        for (int i = 0; i < index - 1; i++) {
            pre = pre.nextNode;
        }
        
        SinglyLinkedListNode *node = [[SinglyLinkedListNode alloc] initWithItem: item];
        
        node.nextNode = pre.nextNode;
        pre.nextNode = node;
    }
}

/**
 刪除節(jié)點(diǎn)
 
 @param item 刪除的元素
 */
- (void)removeNodeWithItem:(NSInteger)item {
    SinglyLinkedListNode *cur = self.headNode;
    
    SinglyLinkedListNode *pre = [[SinglyLinkedListNode alloc] init];
    
    while (cur) {
        if (cur.element == item) {
            // 先判斷此節(jié)點(diǎn)是否是頭節(jié)點(diǎn),如果是頭節(jié)點(diǎn)
            if (cur == self.headNode) {
                self.headNode = cur.nextNode;
            }
            else {
                pre.nextNode = cur.nextNode;
            }
            cur = nil;
            break;
        }
        else {
            pre = cur;
            cur = cur.nextNode;
        }
    }
}

/**
 查詢某個(gè)節(jié)點(diǎn)是否存在
 
 @param item 查詢的元素
 @return 存在返回YES唾那，反之為NO
 */
- (BOOL)searchNodeWithItem:(NSInteger)item {
    SinglyLinkedListNode *cur = self.headNode;
    
    while (cur) {
        if (cur.element == item) {
            return YES;
        }
        else {
            cur = cur.nextNode;
        }
    }
    
    return NO;
}

@end

實(shí)際使用案例


- (void)viewDidLoad {
    [super viewDidLoad];
    
    SinglyLinkedList *lkList = [[SinglyLinkedList alloc] initWithNode: nil];
    
    NSLog(@"%d", [lkList isEmpty]); // 1
    NSLog(@"%ld", [lkList length]); // 0
    
    [lkList appendNodeWithItem: 1];
    NSLog(@"%d", [lkList isEmpty]); // 0
    NSLog(@"%ld", [lkList length]); // 0
    
    [lkList appendNodeWithItem: 2];
    [lkList insertNodeAtHeadWithItem: 8];
    [lkList appendNodeWithItem: 3];
    [lkList appendNodeWithItem: 4];
    [lkList appendNodeWithItem: 5];
    
    [lkList appendNodeWithItem: 6];                 // 8 1 2 3 4 5 6
    [lkList insertNodeWithItem: 9   atIndex: -1];   // 9 8 1 2 3 4 5 6
    [lkList insertNodeWithItem: 100 atIndex: 3];    // 9 8 1 100 2 3 4 5 6
    [lkList insertNodeWithItem: 200 atIndex: 10];   // 9 8 1 100 2 3 4 5 6 200
    [lkList removeNodeWithItem: 100];               // 9 8 1 2 3 4 5 6 200
    
    [lkList travel];
    
    NSLog(@"result: %d", [lkList searchNodeWithItem:200]);
}

寡人的思路

初始化一個(gè)單向鏈表：- (instancetype)initWithNode:(SinglyLinkedListNode *)node;
初始化的時(shí)候可以指定頭節(jié)點(diǎn)，也可以不指定褪尝，不指定頭節(jié)點(diǎn)那么此時(shí)就是一個(gè)空鏈表闹获。
判斷鏈表是否為空：- (BOOL)isEmpty;
單向鏈表的所有操作在實(shí)現(xiàn)的時(shí)候都要從頭節(jié)點(diǎn)入手期犬，所以如果一個(gè)單向鏈表的頭節(jié)點(diǎn)為空，則這個(gè)單向鏈表一定為空避诽，反之則不為空龟虎。
獲取鏈表?yè)碛械目偣?jié)點(diǎn)數(shù)：- (NSInteger)length;
初始化一個(gè) SinglyLinkedListNode * 類型的游標(biāo)指針 cur，讓 cur 在開(kāi)始的時(shí)候指向頭節(jié)點(diǎn)沙庐。我們定義的單向鏈表在尾節(jié)點(diǎn)處指向了 nil 鲤妥，所以 while 循環(huán)的判斷條件 cur 一直到為空時(shí)，則說(shuō)明此時(shí)已經(jīng)遍歷到最后的尾節(jié)點(diǎn)拱雏，那么這個(gè) count 就是鏈表的總節(jié)點(diǎn)數(shù)（長(zhǎng)度）棉安。
遍歷鏈表：- (void)travel;
遍歷鏈表的思路與計(jì)算長(zhǎng)度一樣，都是讓游標(biāo)指針 cur 順著 nextNode 一直遍歷到尾節(jié)點(diǎn)铸抑。
頭插法--在鏈表的頭部插入節(jié)點(diǎn)：- (void)insertNodeAtHeadWithItem:(NSInteger)item;
方法的目的是要把節(jié)點(diǎn) node 插入到鏈表頭部贡耽，即第一個(gè)位置。那么節(jié)點(diǎn) node 在插入成功后就會(huì)成為新的頭節(jié)點(diǎn)羡滑，而原頭節(jié)點(diǎn)則變成新頭節(jié)點(diǎn)的 nextNode 菇爪。
尾插法--在鏈表的尾部插入節(jié)點(diǎn)：- (void)appendNodeWithItem:(NSInteger)item;
- 鏈表為空時(shí)：尾插法就相當(dāng)于給鏈表添加頭節(jié)點(diǎn)。
- 鏈表不為空時(shí)：方法中 while 循環(huán)的判斷條件 cur.nextNode 在遍歷到尾節(jié)點(diǎn)時(shí)為空柒昏，所以當(dāng)循環(huán)停止時(shí) cur 正指向尾節(jié)點(diǎn)凳宙。既然是尾插法，那就讓尾節(jié)點(diǎn)的 nextNode 指向新節(jié)點(diǎn) node 即可职祷。
- 注意：尾插法需要判斷此鏈表是否為空氏涩，如果為空，頭節(jié)點(diǎn)本身就是 nil 有梆，再給它的 nextNode 賦值就變得毫無(wú)意義是尖。而前面的頭插法則不然，即便鏈表為空泥耀，將 self.headNode 賦值給 node.nextNode 也只是相當(dāng)于 node.nextNode = nil 饺汹，這符合單向鏈表的規(guī)則，它既是頭節(jié)點(diǎn)又是尾節(jié)點(diǎn)也就是單節(jié)點(diǎn)的情況痰催。
指定位置插入節(jié)點(diǎn)：- (void)insertNodeWithItem:(NSInteger)item atIndex:(NSInteger)index;
- 位置索引小于或等于 0 時(shí)：將新節(jié)點(diǎn)插入到頭節(jié)點(diǎn)兜辞，調(diào)用頭插法即可。
- 位置索引大于長(zhǎng)度減 1時(shí)：即位置所以已越界夸溶，將新節(jié)點(diǎn)插入到尾節(jié)點(diǎn)逸吵，調(diào)用尾插法即可。
- 非頭尾節(jié)點(diǎn)時(shí)：在指定位置插入節(jié)點(diǎn)缝裁，那就需要將新節(jié)點(diǎn) node 插入到索引 index 處節(jié)點(diǎn)和它前面的節(jié)點(diǎn)之間扫皱。前面節(jié)點(diǎn)的 nextNode 應(yīng)該指向 node ，node 的 nextNode 指向索引 index 處的節(jié)點(diǎn)，這樣才算是在指定位置插入韩脑。所以我們必須已知索引 index 處節(jié)點(diǎn)和其前面的節(jié)點(diǎn)氢妈，這樣在構(gòu)造 for 循環(huán)的時(shí)候，就必須讓循環(huán)次數(shù)為 index - 1扰才，這樣在循環(huán)結(jié)束時(shí)我們拿到的是 index 位置前面的節(jié)點(diǎn)允懂，又可以利用它的 nextNode 拿到 index 處的節(jié)點(diǎn)。
刪除節(jié)點(diǎn)：- (void)removeNodeWithItem:(NSInteger)item;
- 代碼中 cur 指向?qū)h除的節(jié)點(diǎn)衩匣，pre 指向其前一個(gè)節(jié)點(diǎn)蕾总。
- 刪除節(jié)點(diǎn)的核心思路在于，要把將刪除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)和后一個(gè)節(jié)點(diǎn)連接起來(lái)琅捏。
- 舉個(gè)例子：比如鏈表 node0→node1→node2→nil生百，想要?jiǎng)h除node1，就要把 node0 和 node2 連接起來(lái)柄延，即讓 node0.nextNode 指向 node2 蚀浆。node2 可以通過(guò) node1.nextNode 獲取，但是如果只有一個(gè)指向 node1 的游標(biāo) cur 則取不到 node0 搜吧，所以還需要一個(gè)指向 node1 前一個(gè)節(jié)點(diǎn) node0 的游標(biāo) pre市俊。
- 刪除時(shí)要考慮兩種情況：刪除頭節(jié)點(diǎn) / 刪除非頭節(jié)點(diǎn)。前面剛剛說(shuō)的是非頭節(jié)點(diǎn)的情況滤奈。如果刪除的是頭節(jié)點(diǎn)摆昧，那么就不需要考慮 pre 指針，直接讓頭節(jié)點(diǎn)指向它的下一個(gè)節(jié)點(diǎn)即可蜒程。
查詢某個(gè)節(jié)點(diǎn)是否存在：- (BOOL)searchNodeWithItem:(NSInteger)item;
沒(méi)啥可說(shuō)的绅你，就老老實(shí)實(shí)順著節(jié)點(diǎn)的 nextNode 一直往下找就行了，找到就返回 YES 昭躺，找不到就返回 NO忌锯。

單向循環(huán)鏈表

摘自《維基百科》
?
在一個(gè)循環(huán)鏈表中, 首節(jié)點(diǎn)和末節(jié)點(diǎn)被連接在一起。這種方式在單向和雙向鏈表中皆可實(shí)現(xiàn)领炫。要轉(zhuǎn)換一個(gè)循環(huán)鏈表偶垮，你開(kāi)始于任意一個(gè)節(jié)點(diǎn)然后沿著列表的任一方向直到返回開(kāi)始的節(jié)點(diǎn)。再來(lái)看另一種方法帝洪，循環(huán)鏈表可以被視為“無(wú)頭無(wú)尾”似舵。這種列表很利于節(jié)約數(shù)據(jù)存儲(chǔ)緩存，假定你在一個(gè)列表中有一個(gè)對(duì)象并且希望所有其他對(duì)象迭代在一個(gè)非特殊的排列下碟狞。
?
循環(huán)鏈表中第一個(gè)節(jié)點(diǎn)之前就是最后一個(gè)節(jié)點(diǎn)，反之亦然婚陪。循環(huán)鏈表的無(wú)邊界使得在這樣的鏈表上設(shè)計(jì)算法會(huì)比普通鏈表更加容易族沃。對(duì)于新加入的節(jié)點(diǎn)應(yīng)該是在第一個(gè)節(jié)點(diǎn)之前還是最后一個(gè)節(jié)點(diǎn)之后可以根據(jù)實(shí)際要求靈活處理，區(qū)別不大(詳見(jiàn)下面實(shí)例代碼)。當(dāng)然脆淹，如果只會(huì)在最后插入數(shù)據(jù)（或者只會(huì)在之前）常空，處理也是很容易的。
?
另外有一種模擬的循環(huán)鏈表盖溺，就是在訪問(wèn)到最后一個(gè)節(jié)點(diǎn)之后的時(shí)候漓糙，手工的跳轉(zhuǎn)到第一個(gè)節(jié)點(diǎn)。訪問(wèn)到第一個(gè)節(jié)點(diǎn)之前的時(shí)候也一樣烘嘱。這樣也可以實(shí)現(xiàn)循環(huán)鏈表的功能昆禽，在直接用循環(huán)鏈表比較麻煩或者可能會(huì)出現(xiàn)問(wèn)題的時(shí)候可以用。

@implementation SinglyCycleLinkedList

/**
 初始化一個(gè)單向循環(huán)鏈表

 @param node 鏈表的頭節(jié)點(diǎn)
 @return 返回一個(gè)已初始化的單向循環(huán)鏈表
 */
- (instancetype)initWithNode:(SinglyCycleLinkedListNode *)node {
    self = [super init];
    
    if (self) {
        self.headNode = node;

        // 判斷node不為空的情況蝇庭，循環(huán)指向自己
        if (node) {
            node.nextNode = node;
        }
    }
    return self;
}

/**
 判斷鏈表是否為空

 @return 為空返回YES醉鳖，反之為NO
 */
- (BOOL)isEmpty {
    return self.headNode == nil;
}

/**
 獲取鏈表?yè)碛械目偣?jié)點(diǎn)數(shù)

 @return 總節(jié)點(diǎn)數(shù)
 */
- (NSInteger)length {
    if ([self isEmpty]) return 0;
    
    SinglyCycleLinkedListNode *cur =  self.headNode;
    
    NSInteger count = 1;
    
    while (cur.nextNode != self.headNode) {
        count++;
        cur = cur.nextNode;
    }
    
    return count;
}

/**
 遍歷鏈表
 */
- (void)travel {
    // 空鏈表的情況
    if ([self isEmpty]) return;
    
    SinglyCycleLinkedListNode *cur = self.headNode;
    
    while (cur.nextNode != self.headNode) {
        NSLog(@"%ld", cur.element);
        cur = cur.nextNode;
    }
    
    // 退出循環(huán)，cur指向尾節(jié)點(diǎn)哮内，但尾節(jié)點(diǎn)的元素未打印
    NSLog(@"%ld", cur.element);
}

/**
 頭插法：在鏈表的頭部插入節(jié)點(diǎn)

 @param item 插入的元素
 */
- (void)insertNodeAtHeadWithItem:(NSInteger)item {
    SinglyCycleLinkedListNode *node = [[SinglyCycleLinkedListNode alloc] initWithItem: item];
    
    if ([self isEmpty]) {
        self.headNode = node;
        node.nextNode = node;
    }
    else {
        SinglyCycleLinkedListNode *cur = self.headNode;
        
        while (cur.nextNode != self.headNode) {
            cur = cur.nextNode;
        }
        
        // 利用循環(huán)將游標(biāo)指向尾節(jié)點(diǎn)，退出循環(huán)
        node.nextNode = self.headNode;
        self.headNode = node;
        cur.nextNode = self.headNode; // cur.nextNode = node;
    }
}

/**
 尾插法：在鏈表的尾部插入節(jié)點(diǎn)

 @param item 插入的元素
 */
- (void)appendNodeWithItem:(NSInteger)item {
    SinglyCycleLinkedListNode *node = [[SinglyCycleLinkedListNode alloc] initWithItem: item];
    
    if ([self isEmpty]) {
        self.headNode = node;
        node.nextNode = node;
    }
    else  {
        SinglyCycleLinkedListNode *cur = self.headNode;
        
        while (cur.nextNode != self.headNode) {
            cur = cur.nextNode; // 讓游標(biāo)指向尾節(jié)點(diǎn)
        }
        
        cur.nextNode = node;
        node.nextNode = self.headNode;
        
    }
}

/**
 指定位置插入節(jié)點(diǎn)

 @param item 插入的元素
 @param index 位置的索引
 */
- (void)insertNodeWithItem:(NSInteger)item atIndex:(NSInteger)index {
    if (index <= 0) {
        [self insertNodeAtHeadWithItem: item];
    }
    else if (index > ([self length] - 1)) {
        [self appendNodeWithItem:item];
    }
    else {
        // 這里需要的就是讓游標(biāo)指向前一個(gè)節(jié)點(diǎn)
        SinglyCycleLinkedListNode *pre = self.headNode;
        
        for (int i = 0; i < index - 1; ++i) {
            pre = pre.nextNode;
        }
        
        SinglyCycleLinkedListNode *node = [[SinglyCycleLinkedListNode alloc] initWithItem: item];
        node.nextNode = pre.nextNode;
        pre.nextNode = node;
    }
}

/**
 刪除節(jié)點(diǎn)

 @param item 刪除的元素
 */
- (void)removeNodeWithItem:(NSInteger)item {
    if ([self isEmpty]) return;
    
    SinglyCycleLinkedListNode *cur = self.headNode;
    SinglyCycleLinkedListNode *pre = [[SinglyCycleLinkedListNode alloc] init];
    
    // 這個(gè)循環(huán)的終點(diǎn)就是cur指向尾節(jié)點(diǎn)
    while (cur.nextNode != self.headNode) {
        if (cur.element == item) {
            if (cur == self.headNode) // 恰好這個(gè)cur指向的是頭節(jié)點(diǎn)
            {
                // 我們需要先找到尾節(jié)點(diǎn)
                SinglyCycleLinkedListNode *rear = self.headNode;
                while (rear.nextNode != self.headNode) {
                    rear = rear.nextNode;
                }
                
                self.headNode = cur.nextNode;
                rear.nextNode = self.headNode;
                
            }
            else {
                pre.nextNode = cur.nextNode;
            }
            return;
        }
        else {
            pre = cur;
            cur = cur.nextNode;
        }
    }
    
    // 退出循環(huán)，cur指向尾節(jié)點(diǎn)
    if (cur.element == item) {
        if (cur == self.headNode) // 證明鏈表只有一個(gè)頭節(jié)點(diǎn)
        {
            self.headNode = nil;
        }
        else {
            pre.nextNode = cur.nextNode;
        }
    }
}

/**
 查詢某個(gè)節(jié)點(diǎn)是否存在

 @param item 查詢的元素
 @return 存在返回YES瞄崇，反之為NO
 */
- (BOOL)searchNodeWithItem:(NSInteger)item {
    if ([self isEmpty]) return NO;
    
    SinglyCycleLinkedListNode *cur = self.headNode;
    
    while (cur.nextNode != self.headNode) {
        if (cur.element == item) {
            return YES;
        }
        else {
            cur = cur.nextNode;
        }
    }
    
    // 循環(huán)結(jié)束盔腔，cur指向尾節(jié)點(diǎn)
    if (cur.element == item) {
        return YES;
    }
    
    return NO;
}

@end

實(shí)際使用案例

- (void)viewDidLoad {
    [super viewDidLoad];
    
    SinglyCycleLinkedList *ll = [[SinglyCycleLinkedList alloc] initWithNode: nil];
    
//    NSLog(@"%d", [ll isEmpty]); // 1
//    NSLog(@"%ld", [ll length]); // 0
    
    [ll appendNodeWithItem: 1];
//    NSLog(@"%d", [ll isEmpty]); // 0
//    NSLog(@"%ld", [ll length]); // 1
    
    [ll appendNodeWithItem: 2];
    [ll insertNodeAtHeadWithItem: 8];
    [ll appendNodeWithItem: 3];
    [ll appendNodeWithItem: 4];
    [ll appendNodeWithItem: 5];
    [ll appendNodeWithItem: 6];
//    [ll travel]; // 8 1 2 3 4 5 6

    [ll insertNodeWithItem: 9 atIndex: -1];
//    [ll travel]; // 9 8 1 2 3 4 5 6

    [ll insertNodeWithItem: 100 atIndex: 3];
//    [ll travel]; // 9 8 1 100 2 3 4 5 6

    [ll insertNodeWithItem: 200 atIndex: 10];
//    [ll travel]; // 9 8 1 100 2 3 4 5 6 200

    [ll removeNodeWithItem: 100];
    [ll travel]; // 9 8 1 2 3 4 5 6 200
    
    NSLog(@"result: %d", [ll searchNodeWithItem:200]); // result: 1
}

寡人的思路

初始化一個(gè)單向循環(huán)鏈表：與單向鏈表相比只是加了一個(gè)判斷，若傳進(jìn)來(lái)的 node 不為空琳拨，讓 node 循環(huán)指向自己瞭恰。也就是頭節(jié)點(diǎn)的 nextNode 指向頭節(jié)點(diǎn)自己。
判斷鏈表是否為空的方法的思路與單向鏈表一致从绘。
獲取鏈表?yè)碛械目偣?jié)點(diǎn)數(shù)：由于循環(huán)鏈表尾節(jié)點(diǎn)的 nextNode 不是指向 nil 而是指向頭節(jié)點(diǎn)寄疏，所以 while 循環(huán)遍歷到尾節(jié)點(diǎn)的條件也隨之改變成 cur.nextNode != self.headNode 。這里不能像單向鏈表那樣 count 從 0 開(kāi)始直接進(jìn)入到 while 循環(huán)計(jì)數(shù)僵井，要先判斷鏈表是否為空陕截，空則 count = 0 那么返回 0，非空則 count 從 1 開(kāi)始計(jì)數(shù)批什。
遍歷鏈表：與單向鏈表相比只是 while 循環(huán)判斷尾節(jié)點(diǎn)的條件不一樣农曲。
頭插法--在鏈表的頭部插入節(jié)點(diǎn)：頭插法的核心目的是讓節(jié)點(diǎn) node 成為新的頭節(jié)點(diǎn)。配合這個(gè)目的需要做三件事：
1驻债、讓 node 的 nextNode 指向原頭節(jié)點(diǎn)乳规。
2、讓 self.headNode 指向新頭節(jié)點(diǎn) node合呐。這是給 node 行加冠大禮暮的，給它正名，不能只做實(shí)際的頭節(jié)點(diǎn)淌实，還要做名義上的頭節(jié)點(diǎn)冻辩。
3猖腕、讓尾節(jié)點(diǎn)的 nextNode 指向新頭節(jié)點(diǎn) node。
?
單向循環(huán)鏈表的頭插法與單向鏈表的頭插法有很大不同恨闪，主要有兩方面原因：
- 循環(huán)鏈表的尾節(jié)點(diǎn)要指向頭節(jié)點(diǎn)倘感。因?yàn)檫@個(gè)條件在構(gòu)造頭插法時(shí)就必須找到尾節(jié)點(diǎn)，讓尾節(jié)點(diǎn)指向頭節(jié)點(diǎn)咙咽。
- 循環(huán)鏈表的頭插法要判斷鏈表是否為空老玛。因?yàn)檠h(huán)鏈表的頭插法需要找到尾節(jié)點(diǎn)，那就依賴于鏈表需要不為空钧敞，如果為空蜡豹，遍歷過(guò)程則變得毫無(wú)意義。所以當(dāng)鏈表為空時(shí)要單獨(dú)處理犁享，讓頭節(jié)點(diǎn)循環(huán)指向自己即可余素。
尾插法--在鏈表的尾部插入節(jié)點(diǎn)：尾插法的中心思想就是讓 node 成為新的尾節(jié)點(diǎn)。為了這個(gè)中心思想首先得考慮鏈表是否為空炊昆，空就讓頭節(jié)點(diǎn)循環(huán)指向自己桨吊，如果是非空的情況則要辦下面這三件事：
- 找到原尾節(jié)點(diǎn)
- 讓原尾節(jié)點(diǎn)的 nextNode 指向新尾節(jié)點(diǎn) node
- 讓新尾節(jié)點(diǎn)的 nextNode 指向頭節(jié)點(diǎn)
指定位置插入節(jié)點(diǎn)：與單向鏈表思路完全一致
刪除節(jié)點(diǎn)：與單向鏈表幾乎一致，區(qū)別在于對(duì)頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的處理凤巨。
- 頭節(jié)點(diǎn)：刪除頭節(jié)點(diǎn)后视乐，需要找到尾節(jié)點(diǎn)，讓尾節(jié)點(diǎn)的 nextNode 指向頭節(jié)點(diǎn)
- 尾節(jié)點(diǎn)：循環(huán)結(jié)束時(shí)剛好指向尾節(jié)點(diǎn)敢茁，所以在循環(huán)內(nèi)并未處理尾節(jié)點(diǎn)佑淀，需要單獨(dú)處理。尾節(jié)點(diǎn)如果就是頭節(jié)點(diǎn)彰檬，說(shuō)明鏈表只有一個(gè)節(jié)點(diǎn)伸刃，那么此時(shí)將其置空即可。反之則只需正常處理逢倍。
查詢某個(gè)節(jié)點(diǎn)是否存在：與單向鏈表的區(qū)別是尋找尾節(jié)點(diǎn)的條件不一樣捧颅，這就導(dǎo)致循環(huán)鏈表需要判斷鏈表是否為空，尾節(jié)點(diǎn)要單獨(dú)處理较雕。

Github完整源碼

單向鏈表
 單向循環(huán)鏈表

參考資料

鏈表-維基百科碉哑，自由的百科全書

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個(gè)濱河市亮蒋，隨后出現(xiàn)的幾起案子扣典，更是在濱河造成了極大的恐慌，老刑警劉巖慎玖，帶你破解...
沈念sama閱讀 206,378評(píng)論 6贊 481
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件贮尖，死亡現(xiàn)場(chǎng)離奇詭異，居然都是意外死亡趁怔，警方通過(guò)查閱死者的電腦和手機(jī)湿硝，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 88,356評(píng)論 2贊 382
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門闰蛔，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)，“玉大人图柏，你說(shuō)我怎么就攤上這事∪瘟” “怎么了蚤吹？”我有些...
開(kāi)封第一講書人閱讀 152,702評(píng)論 0贊 342
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長(zhǎng)随抠。經(jīng)常有香客問(wèn)我裁着，道長(zhǎng)，這世上最難降的妖魔是什么拱她？我笑而不...
開(kāi)封第一講書人閱讀 55,259評(píng)論 1贊 279
?港島之戀（遺憾婚禮）
正文為了忘掉前任二驰，我火速辦了婚禮，結(jié)果婚禮上秉沼，老公的妹妹穿的比我還像新娘桶雀。我一直安慰自己，他們只是感情好唬复，可當(dāng)我...
茶點(diǎn)故事閱讀 64,263評(píng)論 5贊 371
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開(kāi)白布矗积。她就那樣靜靜地躺著，像睡著了一般敞咧。火紅的嫁衣襯著肌膚如雪棘捣。梳的紋絲不亂的頭發(fā)上，一...
開(kāi)封第一講書人閱讀 49,036評(píng)論 1贊 285
城市分裂傳說(shuō)
那天休建，我揣著相機(jī)與錄音乍恐，去河邊找鬼。笑死测砂，一個(gè)胖子當(dāng)著我的面吹牛茵烈，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播邑彪，決...
沈念sama閱讀 38,349評(píng)論 3贊 400
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開(kāi)眼瞧毙，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了寄症？” 一聲冷哼從身側(cè)響起宙彪，我...
開(kāi)封第一講書人閱讀 36,979評(píng)論 0贊 259
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎有巧，沒(méi)想到半個(gè)月后释漆，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 43,469評(píng)論 1贊 300
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡篮迎，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 35,938評(píng)論 2贊 323
?白月光啟示錄
正文我和宋清朗相戀三年男图，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了示姿。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 38,059評(píng)論 1贊 333
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡逊笆，死狀恐怖栈戳，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情难裆，我是刑警寧澤子檀，帶...
沈念sama閱讀 33,703評(píng)論 4贊 323
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站乃戈，受9級(jí)特大地震影響褂痰，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜症虑，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 39,257評(píng)論 3贊 307
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一缩歪、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧谍憔，春花似錦匪蝙、人聲如沸。這莊子的主人今日做“春日...
開(kāi)封第一講書人閱讀 30,262評(píng)論 0贊 19
一樁弒父案骗污，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽(yáng)。三九已至沈条，卻和暖如春需忿，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背蜡歹。一陣腳步聲響...
開(kāi)封第一講書人閱讀 31,485評(píng)論 1贊 262
情欲美人皮
我被黑心中介騙來(lái)泰國(guó)打工屋厘，沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留，地道東北人月而。一個(gè)月前我還...
沈念sama閱讀 45,501評(píng)論 2贊 354
代替公主和親
正文我出身青樓汗洒，卻偏偏與公主長(zhǎng)得像，于是被迫代替她去往敵國(guó)和親父款。傳聞我的和親對(duì)象是個(gè)殘疾皇子溢谤，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 42,792評(píng)論 2贊 345

數(shù)據(jù)結(jié)構(gòu)系列：Objective-C實(shí)現(xiàn)單鏈表

單向鏈表

實(shí)際使用案例

寡人的思路

單向循環(huán)鏈表

實(shí)際使用案例

寡人的思路

Github完整源碼

參考資料

推薦閱讀更多精彩內(nèi)容