簡介
鏈表（Linked List）是一種物理存儲單元上非連續(xù)玲献、非順序的存儲結(jié)構(gòu)，數(shù)據(jù)元素的邏輯順序是通過鏈表中的指針鏈接次序?qū)崿F(xiàn)的亡资。
單鏈表：
雙鏈表：
iOS 數(shù)據(jù)結(jié)構(gòu)之鏈表
這里以單鏈表為主派近，雙鏈表大同小異，不重復(fù)忘嫉。
節(jié)點
在C語言中可以用struct表示，那么在OC中就應(yīng)該用類來表示案腺。這里簡單起見庆冕，就兩個成員，數(shù)據(jù)和下一個指針劈榨。
@interface ListNode : NSObject
// key访递，用來標(biāo)識結(jié)點本身，不需要唯一同辣，默認(rèn)情況下可以用data的hash代替
@property (assign, nonatomic) NSInteger key;
// 數(shù)據(jù)
@property (strong, nonatomic) id data;
// 下一個指針
@property (strong, nonatomic) ListNode *next;
@end
如果創(chuàng)建節(jié)點拷姿，就需要初始化函數(shù)。
- (instancetype)initWithData:(id)data {
self = [super init];
if (self) {
_data = data;
}
return self;
}
+ (instancetype)nodeWithData:(id)data {
return [[[self class] alloc] initWithData:data];
}
頭結(jié)點
對于一個單鏈表來講旱函，頭結(jié)點就代表了這個鏈表本身响巢。所以需要一個頭結(jié)點屬性。
@interface List()
// 頭結(jié)點
@property (strong, nonatomic) ListNode *headNode;
@end
添加節(jié)點
可以固定在頭部添加棒妨，這也符合最新使用的原則踪古。
另外提供一個方便方法，將數(shù)組中的值連續(xù)添加進(jìn)去券腔。
// 添加節(jié)點伏穆，加在頭部
- (void)addNode:(ListNode *)node {
// 空節(jié)點不需要添加
if (node == nil) {
return;
}
// key可以重復(fù)，可以相同纷纫，沒必要檢查是否存在
// 添加到頭部
if (self.head != nil) {
node.next = self.head;
self.head = node;
} else {
self.head = node;
}
}
// 方便方法枕扫，添加一組節(jié)點
- (void)addNodes:(NSArray *)datas {
[datas enumerateObjectsUsingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
[self addNode:[ListNode nodeWithData:obj]];
}];
}
讀取所有節(jié)點
遍歷鏈表，打印信息辱魁，同時返回節(jié)點數(shù)組烟瞧。
// 讀取所有節(jié)點
- (NSArray *)readAllNodes {
NSMutableArray *nodes = [NSMutableArray array];
ListNode *temp = self.head;
while (temp) {
[nodes addObject:temp];
NSLog(@"node key:%ld; node data: %@", (long)temp.key, temp.data);
temp = temp.next;
}
return [nodes copy];
}
倒序排列
對于單鏈表，討論最多的就是倒序輸出染簇。倒序輸出理解起來確實比較麻煩燕刻。
需要引入previous, current, next三個指針輔助理解，相對簡單一點:
將下一個保存在
next中剖笙。next = current.next;反轉(zhuǎn)：將下一個指向前一個卵洗。
current.next = previous;移動：前一個移動到當(dāng)前。
previous = current;移動：當(dāng)前移動到下一個弥咪。
current = next;
循環(huán)之后过蹂，current已經(jīng)移動到最后，previous就是新的頭
// 倒序
- (void)reverse {
ListNode *previous = nil;
ListNode *current = self.head;
ListNode *next = nil;
while (current) {
// 1. 將下一個保存在`next`中聚至。
next = current.next;
// 2. 反轉(zhuǎn)：將下一個指向前一個酷勺。
current.next = previous;
// 3. 移動：前一個移動到當(dāng)前。
previous = current;
// 4. 移動：當(dāng)前移動到下一個扳躬。
current = next;
}
// current已經(jīng)移動到最后脆诉，previous就是新的頭
self.head = previous;
}
測試
// 生成鏈表
- (IBAction)generateButtonTouched:(id)sender {
NSString *input = self.inputTextView.text;
NSArray *array = [input componentsSeparatedByString:@","];
[self.list addNodes:array];
NSArray *nodes = [self.list readAllNodes];
NSMutableArray *messages = [NSMutableArray array];
[nodes enumerateObjectsUsingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
ListNode *node = (ListNode *)obj;
NSString *message = [NSString stringWithFormat:@"%@", node.data];
[messages addObject:message];
}];
self.listLabel.text = [messages componentsJoinedByString:@";"];
}
// 反向鏈表
- (IBAction)reverseButtonTouched:(id)sender {
[self.list reverse];
NSArray *nodes = [self.list readAllNodes];
NSMutableArray *messages = [NSMutableArray array];
[nodes enumerateObjectsUsingBlock:^(id _Nonnull obj, NSUInteger idx, BOOL * _Nonnull stop) {
ListNode *node = (ListNode *)obj;
NSString *message = [NSString stringWithFormat:@"%@", node.data];
[messages addObject:message];
}];
self.reverseLabel.text = [messages componentsJoinedByString:@";"];
}
demo
https://gitee.com/zhangxusong888/ObjectCDemo/tree/master/AlgorithmDemo
