链表-单链表

概念

• n个节点离散分配
• 彼此通过指针相连
• 每个节点只有一个前驱节点，每个节点只有一个后续节点
• 首节点没有前驱节点，尾节点没有后续节点

专业术语：

-首节点：
第一个有效节点
-尾节点：
最后一个有效节点

• 头节点：
  头结点的数据类型和首节点的类型一样，没有存放有效数据，最最前面的，是在首节点之前的，主要是为了方便对链表的操作(不能确定链表的长度)。
• 头指针：（指向头）
  指向头节点的指针变量
• 尾指针：
  指向尾节点的指针

确定一个链表需要几个参数：

（或者说如果期望一个函数对链表进行操作，我们至少需要接收链表的那些信息？？？）
只需要一个参数:头指针，因为通过它我们可以推出链表的所有信息

链表的分类

• 单链表
• 双链表：每一个节点有两个指针域
• 循环链表：能通过任何一个节点找到其他所有的节点
• 非循环链表

单链表的操作

typedef struct Link{
    int value;
    struct Link * next;
    
}linker;

@interface ViewController ()

@end

@implementation ViewController

- (void)viewDidLoad {
    [super viewDidLoad];
    // Do any additional setup after loading the view.
    linker * link=createLinker();
    traverseLinker(link);
    findLinker(link,5);
    changeNode(link,5);
    traverseLinker(link);
    deleteNode(link,5);
    traverseLinker(link);
    addNode(link,5);
    traverseLinker(link);
    
    linkerLength(link);
}

linker * createLinker() {
    
    linker * link = (linker*) malloc(sizeof(linker));//创建一个头节点
    
    linker * temp = link;//申明一个指针指向头节点，用于遍历链表
    for (int i = 1; i<10; i++) {
        
        linker * a = (linker *)malloc(sizeof(linker));
        a->value = i;
        a->next = NULL;
        temp->next = a;
        temp = temp->next;
    }
    
    return link;
}

void traverseLinker(linker * header){
    
    linker * p = header->next;
    while (p != NULL) {
        printf("i=%d\n",p->value);
        p = p->next;
    }
}

//找到指定的节点
void findLinker(linker * header,int index){
    
    linker * p = header->next;
    int i = 0;
    while (p != NULL) {
        printf("value=%d\n",p->value);
        if (i == index) {
            printf("找到了i=%d value=%d\n",i,p->value);
            break;
        }
        i++;
        p = p->next;
        
    }
}

//修改指定节点数据
void changeNode(linker * header,int index){
    
    linker * p = header->next;
    int i = 0;
    while (p != NULL) {
        printf("value=%d\n",p->value);
        if (i == index) {
            printf("找到了i=%d value=%d\n",i,p->value);
            //linker * temp = p;
            p->value = 99;
            break;
        }
        i++;
        p = p->next;
        
    }
}

//删除指定节点数据
void deleteNode(linker * header,int index){
    
    int i = 0;
    linker * p = header->next;//首节点
    if (header == NULL) {
        printf("为空");
    }
    while (p != NULL && i < index-1) {//每个p都是一个结点
        printf("delete i=%d value=%d\n",i,p->value);
        
        i++;
        p = p->next;
    }
    linker * temp = p->next;//将p的下一个地址复制给temp
    p->next = temp->next;//将下一个的再下一个复制给p的下一个
    free(temp);
}


//添加指定节点数据
void addNode(linker * header,int index){
    
    int i = 0;
    linker * p = header->next;//首节点
    if (header == NULL) {
        printf("为空");
    }
    while (p != NULL && i < index-1) {//每个p都是一个结点
        printf("add i=%d value=%d\n",i,p->value);
        
        i++;
        p = p->next;
    }
    linker * newLink = (linker*)malloc(sizeof(linker));//新建
    newLink->next = NULL;
    newLink->value = 100;
    
    
    linker * q = p->next;//临时变量保存
    p->next = newLink;//p的next指向新建
    newLink->next = q;//新建的next指向之前的p next
    
    
}

//判断链表是否为空
bool isEmpty(linker * link){
    if (link->next == NULL) {//如果头节点的指针域为空，那么肯定就是空链表
        return true;
    }
    return false;
}

//链表长度
int linkerLength(linker * link){
    int i = 0;
    linker * p = link->next;
    while (p != NULL) {
        i++;
        p = p->next;
    }
    printf("length = %d",i);
    return i;
}