數(shù)據(jù)結(jié)構(gòu)-雙向鏈表

（一）什么是鏈表虚循？

鏈表是線性表的一種，所謂的線性表包含順序線性表和鏈表样傍，順序線性表是用數(shù)組實(shí)現(xiàn)的邮丰，在內(nèi)存中有順序排列，通過改變數(shù)組大小實(shí)現(xiàn)铭乾。而鏈表不是用順序?qū)崿F(xiàn)的剪廉，用指針實(shí)現(xiàn)，在內(nèi)存中不連續(xù)炕檩。意思就是說斗蒋，鏈表就是將一系列不連續(xù)的內(nèi)存聯(lián)系起來，將那種碎片內(nèi)存進(jìn)行合理的利用笛质，解決空間的問題泉沾。

所以，鏈表允許插入和刪除表上任意位置上的節(jié)點(diǎn)妇押，但是不允許隨即存取跷究。鏈表有很多種不同的類型：單向鏈表、雙向鏈表及循環(huán)鏈表敲霍。

1俊马、那么先從單向鏈表著手丁存，先看看單向鏈表的模擬圖：

image.png

單向鏈表包含兩個(gè)域，一個(gè)是信息域柴我，一個(gè)是指針域解寝。也就是單向鏈表的節(jié)點(diǎn)被分成兩部分，一部分是保存或顯示關(guān)于節(jié)點(diǎn)的信息艘儒，第二部分存儲下一個(gè)節(jié)點(diǎn)的地址聋伦，而最后一個(gè)節(jié)點(diǎn)則指向一個(gè)空值。

2界睁、雙向鏈表：

image.png

從上圖可以很清晰的看出觉增，每個(gè)節(jié)點(diǎn)有2個(gè)鏈接，一個(gè)是指向前一個(gè)節(jié)點(diǎn)（當(dāng)此鏈接為第一個(gè)鏈接時(shí)翻斟，指向的是空值或空列表）逾礁，另一個(gè)則指向后一個(gè)節(jié)點(diǎn)（當(dāng)此鏈接為最后一個(gè)鏈接時(shí)，指向的是空值或空列表）杨赤。意思就是說雙向鏈表有2個(gè)指針敞斋，一個(gè)是指向前一個(gè)節(jié)點(diǎn)的指針截汪，另一個(gè)則指向后一個(gè)節(jié)點(diǎn)的指針疾牲。

3、循環(huán)鏈表：

image.png

循環(huán)鏈表就是首節(jié)點(diǎn)和末節(jié)點(diǎn)被連接在一起衙解。循環(huán)鏈表中第一個(gè)節(jié)點(diǎn)之前就是最后一個(gè)節(jié)點(diǎn)阳柔，反之亦然。

YYCache用到的雙向鏈表

鍵值對存儲操作

通過創(chuàng)建鏈表節(jié)點(diǎn)node蚓峦，進(jìn)行間接操作數(shù)據(jù)

#pragma mark - _YYLinkedMapNode
@interface _YYLinkedMapNode : NSObject {
    // 類似C中的private_extern舌剂，使用@private的話，限制太大暑椰，@package在類的鏡像外進(jìn)行引用就會報(bào)錯(cuò)
    // 使用@public @protect等的話霍转，就沒什么限制的
    // 目的是，限制在本文件中使用
    @package
    __unsafe_unretained _YYLinkedMapNode *_prev; // 通過dic進(jìn)行持有
    __unsafe_unretained _YYLinkedMapNode *_next; // 通過dic進(jìn)行持有
    id _key;
    id _value;
    NSUInteger _cost;
    NSTimeInterval _time;
}
@end

https://blog.csdn.net/Jasmine_shine/article/details/44033947

最后編輯于：2018.12.27 15:22:19

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