阅读目录
- 为什么要使用链表
- 链表的存储结构
- 链表的常用操作代码实现
1.为什么使用链表
通过上一篇的学习，我们知道顺序表存在一些问题，主要有以下两个方面。
- 顺序表的长度是固定的，如果超出分配的长度就会造成溢出，如果存放的数据太少则会造成空间浪费。
- 在插入元素和删除元素时（尤其不在尾部时），会移动大量的元素，造成性能和效率低下。
基于以上问题，使用链表可以很好地避免顺序表中出现的问题。这也是我们要使用链表的原因。
2.链表的存储结构
单链表的存储结构.jpg
从上图可以看出，单链表中的每个结点都包含一个“数据域”和一个“指针域”。“数据域”中包含当前结点的数据，“指针域”包含下一节点的存储地址，头指针head是指向开始结点的，结束结点没有后继结点，所以结束结点的指针域为空，即null。
3.链表的常用操作及实现代码
链表常用的操作有：
1，插入结点到表头
思路：将head头指针的next指针给新增结点的next，然后将整个新增结点给head头指针的next。因此时间复杂度为O(1)。
插入节点到表头.jpg
2，插入结点到表尾
思路：插入方法与插入到表头一样，只不过多一个步骤就是通过head头指针循环找到终端结点。因此时间复杂度为O(n)。
插入节点到表尾.jpg
3，插入结点(1≤i≤ListLength(L))
思路：插入方法与插入到表头一样，多循环查找当前结点的动作。因此时间复杂度为O(n)。
插入节点.jpg
4，删除结点
思路：同插入结点一样，时间复杂度为O(n)。
删除节点.jpg
5，查找结点
思路：与插入结点和删除结点方法类似，时间复杂度为O(n)。
6，获取链表长度
思路：不像顺序表是连续存储的，获取表的长度非常容易。在链表中，数据不是连续存储的，因此需要循环遍历才能求得链表的长度，所以时间复杂度为O(n)。
实现代码(OC版):
Node.h文件
#import <Foundation/Foundation.h>
#import "Student.h"
@interface Node : NSObject
@property (nonatomic,strong)Student *data;//数据
@property (nonatomic,strong)Node *next; //指针
@end
@interface BllHelper: NSObject
+(Node *)InsertFirst:(Node *)linkList data:(Student *)data;
+(Node *)InsertEnd:(Node *)linkList data:(Student *)data;
+(Node *)Insert:(Node *)linkList key:(NSString *)name data:(Student *)data;
+(Node *)Delete:(Node *)linkList key:(NSString *)name;
+(Node *)GetNodeByName:(Node *)linkList key:(NSString *)name;
+(NSInteger)GetLinkLength:(Node *)linkList;
+(Node *)GetLastNode:(Node *)linkList;
@end
Node.m文件
#import "Node.h"
@implementation Node
-(NSString *)description
{
Node *p = self;
NSLog(@"学生名字:%@,年龄:% ld",p.data.name,p.data.age);
while (p.next) {
p = p.next;
NSLog(@"学生名字:%@,年龄:% ld",p.data.name,p.data.age);
}
return nil;
}
@end
@implementation BllHelper
/**
插入节点在表头
*/
+(Node *)InsertFirst:(Node *)linkList data:(Student *)data
{
Node *first = [Node new];
first.data = data;
if (linkList == nil) {
linkList = first;
return linkList;
}
first.next = linkList;
return first;
}
/**
插入节点在表尾
*/
+(Node *)InsertEnd:(Node *)linkList data:(Student *)data
{
Node *endNode = [[Node alloc]init];
endNode.data = data;
endNode.next = nil;
if (linkList == nil) {
linkList = endNode;
return linkList;
}
[self GetLastNode:linkList].next = endNode;
return linkList;
}
/**
插入结点(在包含关键字name的结点之后插入新的结点)
*/
+(Node *)Insert:(Node *)linkList key:(NSString *)name data:(Student *)data
{
if (linkList == nil) {
return nil;
}
if ([linkList.data.name isEqualToString:name]) {
Node *tempNode = [Node new];
tempNode.data = data;
tempNode.next = linkList.next;
linkList.next = tempNode;
}
[self Insert:linkList.next key:name data:data];
return linkList;
}
/**
删除结点(包含关键字name的结点)
@param linkList <#linkList description#>
@param name <#name description#>
@return <#return value description#>
*/
+(Node *)Delete:(Node *)linkList key:(NSString *)name
{
Node *p = linkList , *w;
while (p.next && ![p.data.name isEqualToString:name]) {
w = p;
p = p.next;
}
w.next = p.next;
return linkList;
}
/**
//查找结点(查找包含关键字name的结点)
*/
+(Node *)GetNodeByName:(Node *)linkList key:(NSString *)name
{
Node *node;
if (linkList == nil) {
return nil;
}
if ([linkList.data.name isEqualToString:name]) {
return linkList;
}
return [self GetNodeByName:linkList.next key:name];
}
// 获取节点的长度
+(NSInteger)GetLinkLength:(Node *)linkList
{
NSInteger i = 1;
Node *p = linkList;
while (p.next) {
p = p.next;
++i;
}
return i;
}
//获取最后一个节点
+(Node *)GetLastNode:(Node *)linkList
{
Node *p = linkList;
while (p.next) {
p = p.next;
}
return p;
}
@end
main.m:
#import <Foundation/Foundation.h>
#import "Student.h"
#import "Node.h"
int main(int argc, const char * argv[]) {
@autoreleasepool {
// insert code here...
//
Student *stu = [[Student alloc]init];
stu.name = @"小明";
stu.age = 22;
Student *stu1 = [[Student alloc]init];
stu1.name = @"小丽";
stu1.age = 25;
Student *stu2 = [[Student alloc]init];
stu2.name = @"小王";
stu2.age = 34;
Student *stu3 = [[Student alloc]init];
stu3.name = @"小涨";
stu3.age = 34;
Node *node;// = [Node new];
NSLog(@"插入节点在表头");
node= [BllHelper InsertFirst:node data:stu];
node= [BllHelper InsertFirst:node data:stu1];
node= [BllHelper InsertFirst:node data:stu2];
NSLog(@"插入节点在表尾");
// node = [BllHelper InsertEnd:node data:stu];
NSLog(@"插入结点(在包含关键字key的结点之前插入新的结点)");
// node = [BllHelper Insert:node key:@"小丽" data:stu3];
NSLog(@"删除结点(删除包含关键字key的结点)");
// node = [BllHelper Delete:node key:@"小丽"];
NSLog(@"查找结点(查找包含关键字key的结点)");
// node = [BllHelper GetNodeByName:node key:@"小丽"];
NSLog(@"获取链表长度");
NSLog(@"%lld",[BllHelper GetLinkLength:node ]);
}
return 0;
}
