单链表-OC实现

单链表 (OC实现)

节点定义 .h文件

//结点
@interface LinkNode : NSObject
//data
@property (nonatomic, assign) int data;
//next
@property (nonatomic, strong, nullable) LinkNode *next;

- (instancetype)initWithData:(int)data;

@end

结点定义 .m文件

@implementation LinkNode
- (instancetype)initWithData:(int)data {
    self = [super init];
    if (self) {
        self.data = data;
        self.next = nil;
    }
    return self;
}
@end

单链表linkList定义

linkList.h文件

@interface LinkList : NSObject
//头结点
@property (nonatomic, strong, readonly) LinkNode *head;
//初始化
- (instancetype)initWithNode:(LinkNode *)node;
//删除
- (void)deleteLinkList:(int)index;
//定位
- (int)locationLinkList:(LinkNode *)node;
//读取元素
- (LinkNode *)getLinkList:(int)index;
//插入
- (void)insertLinkList:(int)data index:(int)index;
//求表长
- (NSInteger)lengthLinkList;

//建表 尾插法 头插法
- (void)createLinkList:(NSArray *)arr;

@end

linkList.m文件

@interface LinkList ()
@property (nonatomic, assign) NSInteger length;
@property (nonatomic, strong, readwrite) LinkNode *head;
@end

链表初始化

//初始化
- (instancetype)initWithNode:(LinkNode *)node {
    self = [super init];
    if (self) {
        self.length = 0;
        self.head = node;
    }
    return self;
}

建表 头插发

- (void)createLinkList:(NSArray *)arr {
    self.length = arr.count;
    for (int i = 0; i<arr.count; i++) {
        LinkNode *node = [[LinkNode alloc] initWithData:[arr[i] intValue]];
        node.next = self.head.next;
        self.head.next = node;
    }
}

删除操作

- (void)deleteLinkList:(int)index {
    if (index > self.length) {
        return;
    }
    int k = 1;
    LinkNode *p = self.head.next;
    while (p.next != nil && k != index-1) {//找到待删前驱
        p = p.next;
        k++;
    }
    LinkNode *d = p.next;
    p.next = d.next;
    self.length--;
}

插入

- (void)insertLinkList:(int)data index:(int)index {
    LinkNode *p = self.head.next;
    int k = 1;
    while (p.next != nil && k != index-1) {//找到待插入前驱
        k++;
        p = p.next;
    }
    if (k == index-1) {
        LinkNode *node = [[LinkNode alloc] initWithData:data];
        node.next = p.next;
        p.next = node;
    }
    self.length++;
}

读取元素

- (LinkNode *)getLinkList:(int)index {
    LinkNode *current = self.head.next;//首结点
    int k = 1;
    while (current.next != nil && k != index) {
        k++;
        current = current.next;
    }
    if (k == index) {
        return current;
    }
    return nil;
}

定位

- (int)locationLinkList:(LinkNode *)node {
    if (node == nil) {
        return -1;
    }
    int k = 1;
    LinkNode *current = self.head.next;//首结点
    while (current.next != nil && node.data != current.data) {
        k++;
        current = current.next;
    }
    if (current) {
        return k;
    }
    return -1;
}

求表长

- (NSInteger)lengthLinkList {
    return self.length;
}