Object-c 单链表的操作

• 如果一个节点指向另一个节点的指针作为数据成员，那么多个这样的结点可以连接起来用一个变量能够访问整个节点序列。这样的节点序列就是最常用的链表实现方法。链表是一种由节点组成的数据结构，每一个节点都包含某些信息及指向链表中的另一个结点的指针。如果序列中的节点只包含后继节点的链接，该链表则称为单向链表。

• 链表包含两个数据成员：info 与 next。info用于存储数据，next用于将节点链接起来。

• 代码翻译如下：

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface LinkedList : NSObject

@property(strong,nonatomic,nullable) LinkedList* next;
@property(strong,nonatomic,nullable) NSObject* data;

/**
 初始化链表
 */
-(instancetype) initLinkedList:(NSObject*) data next:(LinkedList*) next;


/**
 在指定结点之后插入结点
 */
-(void) insertAfterNode:(LinkedList*) indexNode;

/**
 头插法建表
 */
-(void) insertHead:(LinkedList*) node;

-(void) deleteNode:(LinkedList*) node;

@end

NS_ASSUME_NONNULL_END

#import "LinkedList.h"

@implementation LinkedList

- (instancetype)init{
    self = [super init];
    if (self) {
        self.data = nil;
        self.next = nil;
    }
    return self;
}

-(instancetype) initLinkedList:(NSObject*) data next:(LinkedList*) node{
    self = [super init];
    if (self) {
        self.data = data;
        self.next = node;
    }
    return self;
}

-(void) insertAfterNode:(LinkedList*) indexNode{
    
    LinkedList *head = self;
    while (head.next != nil) {
        head = head.next;
    }
    head.next = indexNode;
    indexNode.next = nil;

}

- (void)insertHead:(LinkedList *)node{
    LinkedList *head = self;
    node.next = head.next;
    head.next = node;
}

-(void)deleteNode:(LinkedList *)node{
    LinkedList *p = self.next;
    while (p.next != nil) {
        if ([p.next.data isEqual: node.data]) {
            node.next = p.next.next;
            p.next = node.next;
            break;
        }else{
            p = p.next;
        }
    }
}

@end

• 测试例子：

#import "DataStructVC.h"
#import "LinkedList.h"

@interface DataStructVC ()
@property(nonatomic,strong)LinkedList* head;
@property(nonatomic,assign) NSInteger i;

@end

@implementation DataStructVC

- (void)viewDidLoad {
    [super viewDidLoad];
    UIButton* btnOppo = [[UIButton alloc] initWithFrame:CGRectMake(30, 100, 130, 30)];
    btnOppo.backgroundColor = [UIColor grayColor];
    btnOppo.tag = 10;
    [btnOppo setTitle:@"初始化链表" forState:UIControlStateNormal];
    [btnOppo addTarget:self action:@selector(onClick:) forControlEvents:UIControlEventTouchUpInside];
    [self.view addSubview:btnOppo];
    
    UIButton* next = [[UIButton alloc] initWithFrame:CGRectMake(170, 100, 130, 30)];
    next.backgroundColor = [UIColor grayColor];
    next.tag = 11;
    [next setTitle:@"下一个结点" forState:UIControlStateNormal];
    [next addTarget:self action:@selector(onClick:) forControlEvents:UIControlEventTouchUpInside];
    [self.view addSubview:next];
    
    UIButton* add = [[UIButton alloc] initWithFrame:CGRectMake(30, 150, 130, 30)];
    add.backgroundColor = [UIColor grayColor];
    add.tag = 12;
    [add setTitle:@"add结点" forState:UIControlStateNormal];
    [add addTarget:self action:@selector(onClick:) forControlEvents:UIControlEventTouchUpInside];
    [self.view addSubview:add];
    
    UIButton* delete = [[UIButton alloc] initWithFrame:CGRectMake(170, 150, 130, 30)];
    delete.backgroundColor = [UIColor grayColor];
    delete.tag = 13;
    [delete setTitle:@"删除结点" forState:UIControlStateNormal];
    [delete addTarget:self action:@selector(onClick:) forControlEvents:UIControlEventTouchUpInside];
    [self.view addSubview:delete];

}
-(void)onClick:(UIButton*) button{
    switch (button.tag) {
            
        case 10:{
            [self initLinkList];
        }
            break;
            
        case 11:{
            
            LinkedList* p = self.head;
            while (p.next != nil) {
                
                NSObject* data = p.data;
                LinkedList* next = p.next;
                NSLog(@"47---------cur data :%@ next node:%@",data,next);
                
                p = p.next;
            }
            
        }
            break;
            
        case 12:{
            self.i ++;
            NSString* data = [NSString stringWithFormat:@"p%ld",self.i];
            LinkedList* node = [self buildNode];
            node.data = data;
            //[self.head insertAfterNode:node];
            [self.head insertHead:node];
            
            //node.next = self.head.next;
            //self.head.next = node;
            
            

        }break;
            
        case 13:{
            LinkedList* node = [self buildNode];
            node.data = @"p2";
            [self.head deleteNode:node];
        }break;
            
        default:
            break;
    }
}

-(void) initLinkList{
    self.head = [self buildNode]; //创建一个头结点
    LinkedList* tmpNode = [self buildNode];
    tmpNode.data = @"p0";
    self.head.next = tmpNode;
    self.head.data = @"head";
}

-(LinkedList*) buildNode{
    return [[LinkedList alloc] init];
}



@end

• 例子：就地逆转单链表

-(LinkedList*)reverseList:(LinkedList*) listNode{
    LinkedList* resultList = [self buildNode];
    resultList.next = listNode;
    LinkedList* p = listNode;
    LinkedList* pNext = p.next;
    while (pNext != nil){
        p.next = pNext.next;
        pNext.next = resultList.next;
        resultList.next = pNext;
        pNext = p.next;
    }
    return resultList.next;
}