linked-list-in-C

發表於

前言

linked list 算是資料結構中，需要花時間，但是又非常重要的學習內容

花時間不只是要理解整個結構，而是要對於指標運算以及 struct 型態的靈活運用要有一定程度的瞭解才可以學會她

自己對這塊也有點遺忘，上班後也比較少用，不過剛好藉面試準備的機會，重新複習一下，可能對未來工作使用，或是在某方面有人使用這種方式解決一些問題，都可以更快的步入節奏中

Linked list 與 Array 的比較

  1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance. Also, generally, the allocated memory is equal to the upper limit irrespective of the usage.

  2. Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted.

  • Advantages over arrays
    • Dynamic size
    • Ease of insertion/deletion
  • Drawbacks
    • Random access is not allowed. We have to access elements sequentially starting from the first node. So we cannot do binary search with linked lists efficiently with its default implementation. Read about it here.
    • Extra memory space for a pointer is required with each element of the list.
    • Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

單向 linked list

先了解 單向 linked list 的結構

1
2
3
4
  |-----+-----|        |-----+-----|        |-----+-----|
  |     |     | -----> |     |     | -----> |     |     | -----> NULL
  |-----+-----|        |-----+-----|        |-----+-----|
Head      next1        next1    next2       next2   null

Prototype

1
2
3
4
5
/* define a NODE structure */
typedef struct _NODE {
    DATA data;
    _NODE *next;
}NODE;

Create a node

使用 malloc() 來產生一個 node

理論就是產生一個 node 空間，空間的位址存給 Head
next 指到 NULL

像這樣

1
2
3
4
5
6
7
8
int main(void)
{
    NODE *head = NULL;
    head = (NODE *)malloc(1*sizeof(NODE));

    head->data = INITIAL_DATA;
    head->next = NULL;
}

Insert a node

同樣的理論，使用 malloc() 產生空間，之後產生的空間，必須存放在上一個的 node 的 next 之中，並且當下的 node 中的 next 要存下一個 node 的 pointer address

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void insertNode(struct Node* n, struct DATA datain)
{
    /* Create a space */
    struct Node* insertptr = (struct Node*)malloc(sizeof(struct Node));
    /* store data */
    insertptr->data = datain;
    /* if you insert a node, previous node's next address have to be store to inserted node */
    insertptr->next = n->next;
    /* and previous node's next have to point to insert node */
    n->next = insertptr;
}

/* 透過剛剛的 main() 執行 */
int main(void)
{
    NODE *head = NULL;
    head = (NODE *)malloc(1*sizeof(NODE));

    head->data = INITIAL_DATA;
    head->next = NULL;

    insertNode(head, datain);
}

這樣的動作，如果知道你的其中一個 node 的位址，就可以用上述的 insertNode() 從中插入一個新的節點

Insert node 延伸：push and cat (append)

還記得 push 是什麼嗎？push 就是將新的資料放到 queue 的最前面，其他都順道往後退一格

所以 push 的做法就只要將新的 node 中的 next 指到 原本的 head 並且 renew 真正的 head

1
2
3
4
5
6
7
8
9
10
void push(struct NODE** orig_head, struct DATA datain)
{
    struct NODE* newnode = (struct NODE*)malloc(sizeof(struct NODE));

    newnode->data = datain;
    /* set new node's next ptr */
    newnode->next = *orig_head;
    /* renew new head */
    *orig_head = newnode;
}

而 cat (append) 則是將資料放到最後一個，並將新的 node 中的 next 指到 NULL
同理，可以寫成

1
2
3
4
5
6
7
8
9
10
void cat(struct NODE** last_node, struct DATA datain)
{
    struct NODE* newnode = (struct NODE*)malloc(sizeof(struct NODE);

    newnode->data = datain;
    /* update last node next */
    *last_node->next = newnode;
    /* point new node next to NULL */
    newnode->next = NULL;
}

但這樣其實很鳥，因為你怎麼知道 last_node 是哪一個，所以其實要 search 到 last_node 才對

所以要修改成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void cat(struct NODE** head_ref, struct DATA datain)
{
    struct NODE* newnode = (struct NODE*)malloc(sizeof(struct NODE);
    struct NODE* last = *head_ref;

    newnode->data = datain;
    /* point new node next to NULL */
    newnode->next = NULL;
    
    /* Check head */
    if (*head_ref == NULL)
        *head_ref = newnode;

    /* find last node address */
    while (last->next != NULL)
        last = last->next; 
    
    /* update last node next */
    last->next = newnode;
}

Delete a node

刪除 node 就是 insert node ，做相反的動作

Geeksforgeeks 給予得很有幫助的圖片 (source: https://www.geeksforgeeks.org/linked-list-set-3-deleting-node/)

所以用顛倒的想法，就可以大概寫出來

1
2
3
4
5
6
7
8
9
void delete_node(struct NODE** priv)
{
    struct NODE* tmp = (*priv)->next;

    if (tmp != NULL) {
        (*priv)->next = tmp->next;
        free(tmp);
    }
}

這個大概就是基本的刪除方式，其實也是很容易拉

之後我們就加上 search data 並且如果在 list 中有遇到的都刪掉

1
2
3
4
void delete_node_by_key(struct NODE ** priv, int key)
{
    
}