有些人面试时会被问到数组和链表的区别？试想一下，你知道吗
数组
一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为 O(n)。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。
这个定义里有几个关键词，理解了这几个关键词，我想你就能彻底掌握数组的概念了
-
线性表
顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
image.png
而与它相对立的概念是非线性表，比如二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
image.png
-
连续的内存空间和相同类型的数据
正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。
链表
它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存，空间可扩容，比较常用的是单链表，双链表和循环链表。和数组相比，链表更适合插入、删除操作频繁的场景，查询的时间复杂度较高。不过，在具体软件开发中，要对数组和链表的各种性能进行对比，综合来选择使用两者中的哪一个。
image.png
- 单链表
1）每个节点只包含一个指针，即后继指针。
2）单链表有两个特殊的节点，即首节点和尾节点。为什么特殊？用首节点地址表示整条链表，尾节点的后继指针指向空地址null。
3）性能特点：插入和删除节点的时间复杂度为O（1），查找的时间复杂度为O(n)。
image.png
-
双链表
1）节点除了存储数据外，还有两个指针分别指向前一个节点地址（前驱指针prev）和下一个节点地址（后继指针next）。
2）首节点的前驱指针prev和尾节点的后继指针均指向空地址。
3）性能特点：
和单链表相比，存储相同的数据，需要消耗更多的存储空间。
插入、删除操作比单链表效率更高O(1)级别。以删除操作为例，删除操作分为2种情况：给定数据值删除对应节点和给定节点地址删除节点。对于前一种情况，单链表和双向链表都需要从头到尾进行遍历从而找到对应节点进行删除，时间复杂度为O(n)。对于第二种情况，要进行删除操作必须找到前驱节点，单链表需要从头到尾进行遍历直到p->next = q，时间复杂度为O(n)，而双向链表可以直接找到前驱节点，时间复杂度为O(1)。
对于一个有序链表，双向链表的按值查询效率要比单链表高一些。因为我们可以记录上次查找的位置p，每一次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
image.png
-
循环链表
1）除了尾节点的后继指针指向首节点的地址外均与单链表一致。
2）适用于存储有循环特点的数据，比如约瑟夫问题。
image.png
下面附一个双链表的例子
#import <Foundation/Foundation.h>
@interface Note : NSObject
//上个节点
@property (nonatomic ,strong) Note *previous;
//下个节点
@property (nonatomic ,strong) Note *next;
//当前节点内容
@property (strong , nonatomic) id content;
@end
@interface LinkedList : NSObject
//链表长度
@property (assign , nonatomic) NSUInteger size;
//添加节点
- (void)addObject:(NSObject *)obj;
//插入某节点前
- (void)insertObject:(NSObject *)obj nextObject:(NSObject *)nextObj;
//移除指定节点
- (void)remove:(NSObject *)obj;
//移除指定索引节点
- (void)removeAtIndex:(NSInteger)index;
//获取指定位置的值
- (NSObject *)objectAtIndex:(NSInteger)index;
//链表初始化
+ (instancetype)list;
@end
@implementation Note
@end
#import "LinkedList.h"
#import "Note.h"
@interface LinkedList ()
//首个节点
@property (nonatomic, strong) Note *first;
//最后节点
@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;
}
//新节点
note.previous = self.last;
note.next = nil;
note.content = obj;
//给上一个节点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]; //移除节点
break;
}
tempNote = tempNote.next;
}
}
//根据索引移除元素
- (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]; //移除节点
break;
}
tempNote = tempNote.next;
}
}
- (void)removeNote:(Note *)note
{
//连接上下节点
Note *preNote = note.previous;
Note *nextNote = note.next;
preNote.next = nextNote;
nextNote.previous = preNote;
note.content = nil; //清空被移除节点内容
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
单链表反转和链表中环的检测是面试里面经常涉及到的考点，下面是具体实例
单链表反转（迭代方式）
迭代的方式是从链头开始处理，如下图给定一个存放5个数的链表。
image.png
首先对于链表设置两个指针：
image.png
然后依次将旧链表上每一项添加在新链表的后面，然后新链表的头指针NewH移向新的链表头，如下图所示。此处需要注意，不可以上来立即将上图中P->next直接指向NewH，这样存放2的地址就会被丢弃，后续链表保存的数据也随之无法访问。而是应该设置一个临时指针tmp，先暂时指向P->next指向的地址空间，保存原链表后续数据。然后再让P->next指向NewH，最后P=tmp就可以取回原链表的数据了，所有循环访问也可以继续展开下去。
image.png
指针继续向后移动，直到P指针指向NULL停止迭代。
image.png
最后一步：
image.png
- (Node *)reverseList:(Node *)headNode
{
//链表为空或者仅1个数直接返回
if (headNode == nil || headNode.next == nil)
{
return headNode;
}
Node *p = headNode;
Node *newHead = nil;
//一直迭代到链尾
while (p != nil)
{
//暂存p下一个地址，防止变化指针指向后找不到后续的数
Node *tempNode = p.next;
//p->next指向前一个空间
p.next = newHead;
//新链表的头移动到p，扩长一步链表
newHead = p;
//p指向原始链表p指向的下一个空间
p = tempNode;
}
return newHead;
}
单链表反转（递归方式）
首先指针H迭代到底如下图所示，并且设置一个新的指针作为翻转后的链表的头。由于整个链表翻转之后的头就是最后一个数，所以整个过程NewH指针一直指向存放5的地址空间。
image.png
然后H指针逐层返回的时候依次做下图的处理，将H指向的地址赋值给H->next->next指针，并且一定要记得让H->next =NULL，也就是断开现在指针的链接，否则新的链表形成了环，下一层H->next->next赋值的时候会覆盖后续的值。
image.png
继续返回操作：
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;
}
//一直循环到链尾
Node *newHead = [self reverseSingleList:headNode.next];
//翻转链表的指向
headNode.next.next = headNode;
//记得赋值NULL，防止链表错乱
headNode.next = nil;
//新链表头永远指向的是原链表的链尾
return newHead;
}
链表中环的检测
- 首先设置两个指针，分别命名为fast和slow，fast指针每次向后移2步，slow指针每次向后移1步。
- 如果，fast指针最后走到尾结点，则没有环。
- 如果，fast指针和slow指针相遇，则证明有环。
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;
}
}
最后总结两者区别
先看时间复杂度上的区别
image.png
不过，数组和链表的对比，并不能局限于时间复杂度。而且，在实际的软件开发中，不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。
数组简单易用，在实现上使用连续的内存空间，可以借助CPU的缓冲机制预读数组中的数据，所以访问效率更高，而链表在内存中并不是连续存储，所以对CPU缓存不友好，没办法预读。
数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。
如果代码对内存的使用非常苛刻，那数组就更适合。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。
网友评论