#线性表之链表

---

阅读目录

• 为什么要使用链表
• 链表的存储结构
• 链表的常用操作代码实现

---

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;
}