单向链表笔记

单向链表定义

单向链表是由一个个结点组成的 
每个结点包括数值和指向下一个结点的指针 
头结点数值为null 尾结点指向为null

复制代码

链表和数组的区别

1.数组静态分配内存，链表动态分配内存。
2.数组在内存中是连续的，链表是不连续的。
3.数组利用下标定位，查找的时间复杂度是O(1)，链表通过遍历定位元素。查找的时间复杂度是O(N)。
4.数组插入和删除需要移动其他元素，时间复杂度是O(N)，链表的插入或删不需要移动其他元素，时间复杂度是O(1)。

复制代码

单向链表具体实现

• 定义结点类
  • .h文件

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

/**定义结点 属性包括数值和指向下一个结点的指针*/

@interface Node : NSObject

/**构造方法*/
- (instancetype)initWithData:(NSString*)dataString nextNode:(nullable Node*)nextNode;

@property (nonatomic ,strong) NSString *dataString;//存储数据、暂时为字符串

@property (nonatomic ,strong ,nullable) Node *nextNode;//指向下一个结点

@end

NS_ASSUME_NONNULL_END

复制代码

• .m文件

#import "Node.h"

@implementation Node

- (instancetype)initWithData:(NSString*)dataString nextNode:(nullable Node*)nextNode
{
    self = [super init];
    if (self) {
        self.dataString = dataString;
        self.nextNode = nextNode;
    }
    return self;
}

@end

复制代码

• 定义链表类
  • .h文件

#import <Foundation/Foundation.h>
#import "Node.h"

NS_ASSUME_NONNULL_BEGIN

@interface LinkList : NSObject

@property (nonatomic ,assign) NSInteger num;//链表长度

@property (nonatomic ,strong) Node *firstNode;//头结点 指向第一个数据

/*向指定位置插入数据*/
- (void)addData:(NSString*)dataString atIndex:(NSInteger)index;

/**默认插入到最后*/
- (void)addData:(NSString*)dataString;

/*删除最后一个元素*/
- (void)removeLastObject;

/**删除指定位置元素*/
- (void)removeDataAtIndex:(NSInteger)index;

/*获取对应元素的索引*/
- (NSInteger)indexForDataString:(NSString*)dataString;

/**获取第一个元素*/
- (NSString*)getFirstObject;

/**获取最后一个元素*/
- (NSString*)getLastObject;

/**打印链表元素*/
- (void)printAllData;

/*链表是否为空*/
- (BOOL)isEmpty;

@end

NS_ASSUME_NONNULL_END

复制代码

• .m文件

#import "LinkList.h"

@implementation LinkList

-(instancetype)init
{
    self = [super init];
    if (self) {
        /*
         头结点 不存储数据 指向第一个结点
         */
        self.firstNode = [[Node alloc]init];
        self.num = 0;
    }
    return self;
}

//指定位置index 添加元素
- (void)addData:(NSString*)dataString atIndex:(NSInteger)index
{
    if (index > self.num) {
        NSLog(@"不合法");
        return;
    }
    
    ///1.index位置前一个结点
    Node *previousNode = self.firstNode;//头结点
    for (NSInteger i = 0; i <=  index - 1; i ++) {
        previousNode = previousNode.nextNode;
    }
    ///2.index位置结点
    Node *curNode = previousNode.nextNode;
    ///3.创建新的结点 指向index位置的结点
    Node *newNode = [[Node alloc]initWithData:dataString nextNode:curNode];
    previousNode.nextNode = newNode;
    
    self.num++;
}

//默认插入到最后一个
- (void)addData:(NSString*)dataString
{
    Node *node = self.firstNode;
    for (NSInteger i = 0; i < self.num; i ++) {
        node = node.nextNode;
        if (node.nextNode == NULL) {//找到最后一个结点 即指向下一个为空的结点
            Node *newNode = [[Node alloc]initWithData:dataString nextNode:NULL];
            node.nextNode = newNode;
        }
    }
    self.num++;
}

/*删除最后一个元素*/
- (void)removeLastObject
{
    ///最后一个的前一个
    Node *previousNode = self.firstNode;//头结点
    for (NSInteger i = 0; i <=  self.num - 1; i ++) {
        previousNode = previousNode.nextNode;
    }
    
    previousNode.nextNode = NULL;
    
    self.num--;
}

/**删除指定位置元素*/
- (void)removeDataAtIndex:(NSInteger)index
{
    if (index > self.num-1) {
        NSLog(@"不合法");
        return;
    }
    ///1.index位置前一个结点
    Node *previousNode = self.firstNode;//头结点
    for (NSInteger i = 0; i <=  index - 1; i ++) {
        previousNode = previousNode.nextNode;
    }
    ///2.index位置结点
    Node *curNode = previousNode.nextNode;
    ///3.下一个结点
    Node *nextNode = curNode.nextNode;
    //前一个结点 指向下一个
    previousNode.nextNode = nextNode;
    
    self.num--;
}

/*获取对应元素的索引*/
- (NSInteger)indexForDataString:(NSString*)dataString
{
    Node *previousNode = self.firstNode;//头结点
    for (NSInteger i = 0; i <=  self.num - 1; i ++) {
        previousNode = previousNode.nextNode;
        if ([previousNode.dataString isEqualToString:dataString]) {
            return i;
        }
    }
    return -1;
}

/**获取第一个元素*/
- (NSString*)getFirstObject
{
    Node *node = self.firstNode;
    return node.nextNode.dataString;
}

/**获取最后一个元素*/
- (NSString*)getLastObject
{
    Node *node = self.firstNode;
    for (NSInteger i = 0; i < self.num; i ++) {
        node = node.nextNode;
        if (node.nextNode == NULL) {//找到最后一个结点 即指向下一个为空的结点
            return node.dataString;
        }
    }
    
    return nil;
}

//打印链表元素
- (void)printAllData
{
    NSMutableArray *array = [NSMutableArray array];
    Node *node = self.firstNode;
    for (NSInteger i = 0; i < self.num; i ++) {
        node = node.nextNode;
        [array addObject:node.dataString];
    }
    NSLog(@"链表最终数据为：%@",array);
}

//链表是否为空
- (BOOL)isEmpty
{
    return  self.num == 0 ? YES : NO;
}

@end


复制代码

• 测试代码

#import "ViewController.h"
#import "LinkList.h"

@interface ViewController ()

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];

    LinkList *list = [[LinkList alloc]init];
    ///BOOL isTureF =  list.isEmpty; 返回yes
    [list addData:@"a" atIndex:0];
    [list addData:@"b" atIndex:1];
    [list addData:@"c" atIndex:2];

    [list printAllData];// a,b,c

    [list addData:@"d" atIndex:1];

    [list printAllData];// a,d,b,c
    
    NSLog(@"长度为：%ld",(long)list.num);///长度为：4
    
    [list addData:@"e"];
    
    [list addData:@"f"];
    
    [list addData:@"h" atIndex:0];

    [list printAllData];//// h,a,d,b,c,e,f
    
    NSString *first = list.getFirstObject;
    NSLog(@"%@",first);///h
    
    NSString *last = list.getLastObject;
    NSLog(@"%@",last);///f
    
    [list removeDataAtIndex:2];
    
    [list printAllData];// h,a,b,c,e,f
    
    [list removeLastObject];
    
    [list printAllData];// h,a,b,c,e
    
   NSInteger row =  [list indexForDataString:@"b"];
   NSLog(@"%ld",(long)row);//2
    
}


@end

复制代码