单链表基本操作

早前读YYCache源码时候 ,写过一篇文章 : YYCache源码解读,对源码中使用的LRU算法无比钦佩,其中涉及了很多链表操作(源码中是双链表) 这两天看了看链表相关的操作,写了这篇单链表的基本操作的文章.双链表后期会更新,敬请期待!

下面分几方面介绍这篇文章
本篇文章中内容来不及更新的,请移步到GitHub上查看,代码是最新的

1.源码编写

<结点的.h文件>

//
//  LinkNode.h
//  手写链表
//
//  Created by majianjie on 2018/5/6.
//  Copyright © 2018年 majianjie. All rights reserved.
//

#import <Foundation/Foundation.h>

@interface LinkNode : NSObject<NSCopying>
{
    @public
    LinkNode *next;
}

@property (nonatomic,strong)NSString *key;

@property (nonatomic,strong)NSString *value;

- (instancetype)initWithKey:(NSString *)key value:(NSString *)value;

@end

<结点的.m文件>

//
//  LinkNode.m
//  手写链表
//
//  Created by majianjie on 2018/5/6.
//  Copyright © 2018年 majianjie. All rights reserved.
//

#import "LinkNode.h"

@implementation LinkNode

- (instancetype)initWithKey:(NSString *)key value:(NSString *)value{

    if (self = [super init]) {
        _key = key;
        _value = value;
    }
    return self;
}

- (id)copyWithZone:(NSZone *)zone{

    LinkNode *node = [LinkNode allocWithZone:zone];
    node.key = self.key;
    node.value = self.value;
    node->next = self->next;

    return node;

}
@end

<链表的.h文件>

//
//  LinkList.h
//  手写链表
//
//  Created by majianjie on 2018/5/6.
//  Copyright © 2018年 majianjie. All rights reserved.
//

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

@interface LinkList : NSObject



/**
 在头部插入一个结点

 @param node 要插入的结点
 */
- (void)insertNodeAtHead:(LinkNode *)node;

/**
 插入结点

 @param node 结点
 */
- (void)insertNode:(LinkNode *)node;
/**
 移除结点

 @param node 要移除的结点
 */
- (void)removeNode:(LinkNode *)node;

/**
 求链表的长度

 @return 返回链表长度
 */
- (NSInteger)listLength;

/**
 链表反转
 */
- (void)reverse;
/**
 移除所有的结点
 */
- (void)removeAllNode;

/**
 判断链表是否有环

 @param headerNode 链表的头结点
 @return 是否是有环的 1 : 有环   0 : 没环
 */
- (int)isCircleExist:(LinkNode *)headerNode;

/**
 返回链表的头结点

 @return 要返回头结点
 */
- (LinkNode *)headNode;

/**
 返回链表的尾结点

 @return 要返回的尾结点
 */
- (LinkNode *)lastNode;

/**
 返回一个结点前面的结点

 @param node 当前结点
 @return 当前结点前面的结点
 */
- (LinkNode *)nodeBeforeNode:(LinkNode *)node;


/**
 求链表中倒数第k个结点
 思路 : 第一个指针先走 k-1步,然后两个指针一起走,当第一个结点到达尾结点时候 第二个正好走到倒数第 k 结点位置

 @param headNode 链表头结点
 @param k k 值
 @return 返回所找的结点
 */
- (LinkNode *)findkThNode:(LinkNode *)headNode k:(int)k;

@end

<链表的.m文件>

//
//  LinkNode.m
//  手写链表
//
//  Created by majianjie on 2018/5/6.
//  Copyright © 2018年 majianjie. All rights reserved.
//

#import "LinkNode.h"

@implementation LinkNode

- (instancetype)initWithKey:(NSString *)key value:(NSString *)value{

    if (self = [super init]) {

        _key = key;
        _value = value;

    }
    return self;
}

- (id)copyWithZone:(NSZone *)zone{

    LinkNode *node = [LinkNode allocWithZone:zone];
    node.key = self.key;
    node.value = self.value;
    node->next = self->next;

    return node;
}
@end

2.源码使用

// 0. 初始化链表
        LinkList *list = [[LinkList alloc] init];
        for (int i = 1; i <= 9; i++) {
            LinkNode *node = [[LinkNode alloc] initWithKey:[NSString stringWithFormat:@"%d",i] value:[NSString stringWithFormat:@"%d",i*111]];

            [list insertNode:node];
        }


// 1. 求链表中倒数第k个结点
       LinkNode *targetNode = [list findkThNode:[list headNode] k:3];
        if (targetNode) {
            NSLog(@"%@ %@",targetNode.key,targetNode.value);
        }else{
            NSLog(@"传入参数有误");
        }

// 2. 单链表反转

        [list reverse];
        LinkNode *newHeadNode = [list headNode];
        while (newHeadNode) {
            NSLog(@"revertedHeaderNode key:%@   value:%@ ",newHeadNode.key,newHeadNode.value);
            newHeadNode = newHeadNode->next;
        }
// 3. 单链表是否有环
   int isCircle = [list isCircleExist:[list headNode]];
    NSLog(@"链表 %@", isCircle ? @"有环" : @"无环");

还有部分功能操作这两天会更新,今天先写到这里吧.

GitHub地址