iOS 数据结构之单向链表

链表 ,数组 是我们经常碰到的线性数据结构, 是一种真正的动态数据结构 ,而数组是一段连续的内存空间,通过指针偏移去取数组里相邻的数据,而链表是将不同的内存空间,连在在一起,类似于我们生活中常见的火车车厢,每节车厢就可以看做是一个数据,只不过这个数据内部还有个指针指向它下一个节点的数据.

image.png

因此链表需要有个头节点 ,可以方便的进行查询 添加 移除等操作,小编通过学习链表这种数据结构的特点,用 Objective-C 语言实现了一个单向链表,即只有一个头节点 最后一个节点为 NULL.

//
//  LinkedList.h
//  ArrayList
//
//  Created by dzb on 2018/8/3.
//  Copyright © 2018 大兵布莱恩特. All rights reserved.
//

#import <Foundation/Foundation.h>

@interface LinkedList <ObjectType> : NSObject

- (void) addObjectAtFirst:(ObjectType)object;

- (void) addObjectAtLast:(ObjectType)object;

- (void) addObject:(ObjectType)object atIndex:(NSInteger)index;

- (void) updateObject:(ObjectType)object atIndex:(NSInteger)index;

- (BOOL) containObject:(ObjectType)object;

- (ObjectType) objectAtIndex:(NSInteger)index;

- (ObjectType) removeObjectAtIndex:(NSInteger)index;

- (ObjectType) removeFirstObject;

- (ObjectType) removeLastObject;

///count
@property (nonatomic,assign) NSInteger count;
///empty
@property (nonatomic,assign,getter=isEmpty,readonly) BOOL empty;
///firstObject
@property (nonatomic,strong,readonly) ObjectType firstObject;
///lastObject
@property (nonatomic,strong,readonly) ObjectType lastObject;

@end

//
//  LinkedList.m
//  ArrayList
//
//  Created by dzb on 2018/8/3.
//  Copyright © 2018 大兵布莱恩特. All rights reserved.
//

#import "LinkedList.h"

typedef void* AnyObject;

typedef struct node {
    AnyObject data;
    struct node *next;
} Node;

@interface LinkedList ()

///head
@property (nonatomic,assign) Node *dummyHead;
///size
@property (nonatomic,assign) NSInteger size;

@end

@implementation LinkedList

- (instancetype)init
{
    self = [super init];
    if (self) {
        Node * dummyHead = (Node*)malloc(sizeof(Node));
        dummyHead->data = nil;
        dummyHead->next = nil;
        self.dummyHead = dummyHead;
        self.size = 0;
    }
    return self;
}

- (void)addObjectAtFirst:(id)object {
    [self addObject:object atIndex:0];
}

- (void)addObjectAtLast:(id)object {
    [self addObject:object atIndex:self.size];
}

- (void)addObject:(id)object atIndex:(NSInteger)index {
    if (index < 0 || index > self.count) {
        @throw [NSException exceptionWithName:@"LinkedList is out of bounds" reason:@"Add failed. Illegal index." userInfo:nil];
        return;
    }
    Node *prev = self.dummyHead;
    for (int i = 0; i< index; i++) {
        prev = prev->next;
    }
    Node *cur = (Node*)malloc(sizeof(Node));
    cur->data = (__bridge_retained AnyObject)object;
    cur->next = prev->next;
    prev->next = cur;
    self.size++;
}

- (id)objectAtIndex:(NSInteger)index {
    if (index < 0 || index >= self.count) {
        @throw [NSException exceptionWithName:@"LinkedList is out of bounds" reason:@"Add failed. Illegal index." userInfo:nil];
        return nil;
    }
    Node *cur = self.dummyHead->next;
    for (int i = 0; i<index; i++) {
        cur = cur->next;
    }
    return (__bridge_transfer id)cur->data;
}

- (id)firstObject {
    return [self objectAtIndex:0];
}

- (id)lastObject {
    return [self objectAtIndex:self.count-1];
}

- (void)updateObject:(id)object atIndex:(NSInteger)index {
    if (index < 0 || index >= self.count) {
        @throw [NSException exceptionWithName:@"LinkedList is out of bounds" reason:@"Add failed. Illegal index." userInfo:nil];
        return;
    }
    Node *cur = self.dummyHead->next;
    for (int i = 0; i<index; i++) {
        cur = cur->next;
    }
    CFRelease(cur->data);
    cur->data = (__bridge_retained AnyObject)object;
}

- (BOOL)containObject:(id)object {
    Node *cur = self.dummyHead->next;
    while (cur != NULL) {
        id data = (__bridge_transfer id)cur->data;
        if ([data isEqual:object])
            return YES;
        cur = cur->next;
    }
    return NO;
}


- (id) removeObjectAtIndex:(NSInteger)index {
    if (index < 0 || index >= self.count) {
        @throw [NSException exceptionWithName:@"LinkedList is out of bounds" reason:@"Add failed. Illegal index." userInfo:nil];
        return nil;
    }
    Node *prev = self.dummyHead;
    for (int i = 0; i<index; i++) {
        prev = prev->next;
    }
    Node *deleteNode = prev->next;
    prev->next = deleteNode->next;
    id object = (__bridge_transfer id)deleteNode->data;
    free(deleteNode);
    deleteNode = NULL;
    self.size--;
    return object;
}

- (id) removeFirstObject {
    return [self removeObjectAtIndex:0];
}

- (id) removeLastObject {
    return [self removeObjectAtIndex:self.count-1];
}

- (NSInteger)count {
    return self.size;
}

- (NSString *)description {
    
    NSMutableString *string = [NSMutableString stringWithFormat:@"\nLinkedList %p : [ \n" ,self];
    Node *cur = self.dummyHead->next;
    while (cur != nil) {
        [string appendFormat:@"%@ -> \n",cur->data];
        cur = cur->next;
    }
    [string appendString:@"NULL\n"];
    [string appendString:@"]\n"];
    
    return string;
}

- (BOOL)isEmpty {
    return self.count == 0;
}

- (void)dealloc
{
    while (self.count != 0) {
        [self removeFirstObject];
    }
    
}
@end

整个链表才有了头插法往链表里插入一个新的元素,即新来的元素插入到头节点位置, 当创建一个空链表时候 链表的头节点为一个空的 Node ,即 Node->data 和 Node->next 都为 NULL, 这样以后可要根据这个头节点往下查找每个节点的数据,进行增加 删除 修改 和查找的操作. 并管理了对象的引用计数 ,当链表销毁时会对内部的每一个节点进行释放内存的操作,并对节点内管理的对象引用计数进行-1操作,以保证存入链表的 OC 对象能够完美释放内存.

下边是测试用例

- (void) test {
    static int count = 0;
    if (count > 9) {
        [_timer invalidate];
        _timer = nil;
        NSLog(@"time is %@",[_timeArray valueForKeyPath:@"@avg.self"]);
        return;
    }

    dispatch_async(dispatch_get_global_queue(0, 0), ^{
        CFAbsoluteTime startTime = CFAbsoluteTimeGetCurrent();
        int number = 100000;
        Person *p = [Person new];
        LinkedList <Person *> *linked = [[LinkedList alloc] init];
        for (int i = 0; i<number; i++) {
            [linked addObjectAtFirst:p];
        }
        CFAbsoluteTime linkTime = (CFAbsoluteTimeGetCurrent() - startTime);
        CFTimeInterval duration = linkTime * 1000.0f;
        NSLog(@"Linked in %f ms",duration);
        [self->_timeArray addObject:@(duration)];
        count++;
    });
    
}

image.png

往链表里添加10万个 同一个 person 对象 ,实质就是对 person 的引用计数+1 ,当链表销毁时候 再对同一个 person 对象执行 移除操作 ,使其引用计数为 0 ,Person 对象才会立马销毁

好了，我是大兵布莱恩特，欢迎加入博主技术交流群，iOS 开发交流群

QQ20180712-0.png