Link List in C

Chinyu included in Algorithm

2021-09-10 464 words 3 minutes views

Contents

Link List

基本概念

相同結構的東西（用struct)使用指標（pointer)串起來，相同結構的東西稱作NODE
在加入/刪除比array上好操作
有需要的時候才動態的配置空間(malloc / new)
查詢時比array慢

圖示：

靜態配置：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29


#include<stdio.h>
#include<stdlib.h>

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

int main()
{
    Node x, y, z;
    Node *ptr = &x;
    x.data = 10;
    x.next = &y;
    y.data = 20;
    y.next = &z;
    z.data = 30;
    z.next = NULL;

    while(ptr != NULL)
    {
        printf("address=%p, ", ptr);
        printf("data=%d ", ptr->data);
        printf("next=%p\n", ptr->next);
        ptr = ptr -> next;
    }
    return 0;
}

Result:

1
2
3


address=0x7ffeebebd848, data=10 next=0x7ffeebebd838
address=0x7ffeebebd838, data=20 next=0x7ffeebebd828
address=0x7ffeebebd828, data=30 next=0x0

動態配置：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43


#include<stdio.h>
#include<stdlib.h>
struct node{
    int data;
    struct node *next;
};
typedef struct node Node;

int main(int argc, char *argv[])
{
    int num;
    num = atoi(argv[1]);
    Node *first, *cur, *pre;

    for(int i = 0; i < num; i++)
    {
        cur = (Node *)malloc(sizeof(Node));
        cur -> data = i + 1;
        printf("Data for Node%d: %d\n", i + 1, cur -> data);
        if(i == 0) first = cur;
        else pre -> next = cur;
        cur -> next = NULL;
        pre = cur;
    }
    cur = first;
    while(cur != NULL)
    {
        printf("address=%p, ", cur);
        printf("data=%d ", cur->data);
        printf("next=%p\n", cur->next);
        cur = cur -> next;
    }
    // free pointer
    cur = first;
    Node *tmp;
    while (cur != NULL)
    {
        tmp = cur;
        cur = cur->next;
        free(tmp);
    
    return 0;
}

Result:

1
2
3
4
5
6
7
8
9


$ ./Linklist 4
Data for Node1: 1
Data for Node2: 2
Data for Node3: 3
Data for Node4: 4
address=0x7f8748c05840, data=1 next=0x7f8748c05850
address=0x7f8748c05850, data=2 next=0x7f8748c05860
address=0x7f8748c05860, data=3 next=0x7f8748c05870
address=0x7f8748c05870, data=4 next=0x0

搜尋：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10


Node *searchNode(Node *first, int val)
{
    Node *p = first;
    while(p)
    {
        if(p -> data == val) return p;
        else p = p -> next;
    }
    return NULL;
}

插入：插在某節點的後方

1
2
3
4
5
6
7


void insertNode(Node *node, int val)
{
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode -> data = val;
    newNode = node -> next;
    node -> next = newNode;
}

刪除節點：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


Node* delete(Node *first, Node *node)
{
    Node * p = first;
    if(!p) 
    {
        printf("Nothing to delete\n");
        return first;
    }
    if(first == node) first = first->next;
    else
    {
        while(p->next != node)
            p = p -> next;
        p -> next = node -> next;
    }
    free(node);
    return first;
}