# Linked list學習紀錄

###### tags: `資料結構`

Copyright 2021, [月下麒麟](https://hackmd.io/@YMont/note-catalog)

---

## Introduction
[CMU linked list 教材](https://www.andrew.cmu.edu/course/15-121/lectures/Linked%20Lists/linked%20lists.html)
>Each element (we will call it a node) of a list is comprising of two items - the **data** and a reference to the **next node**.
The last node has a reference to null. The entry point into a linked list is called the head of the list.
**It should be noted that head is not a separate node, but the reference to the first node.** If the list is empty then the head is a null reference.

有兩個缺點:
>One disadvantage of a linked list against an array is that it does **not allow direct access to the individual elements.** If you want to access a particular item then you have to start at the head and follow the references until you get to that item.
Another disadvantage is that **a linked list uses more memory compare with an array - we extra 4 bytes (on 32-bit CPU) to store a reference to the next node.**

## Type of linked list
* **Singly** linked list is describe above.
* A **doubly** linked list is a list that has two reference, one to the <u>next node</u> and another to **previous** node.
* **Circular** linked listwhere **last node of the list points back to the first node** (or the head) of the list.

**Example**
`head = head.next;`
`head = head->next;`

`head.next = head.next.next`
`head->next = head->next->next`

`head.next.next.next.next = head`
`head->next->next->next->next = head`

## Operation

### Declaration
Declare a head pointer and make it as NULL

typedef struct _node{
    char data;
    struct node *next;
} node;

node *head = NULL;

程式參考出處:[Inserting a node at the beginning of a linked list](https://www.log2base2.com/data-structures/linked-list/inserting-a-node-at-the-beginning-of-a-linked-list.html)
### addFirst

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

typedef struct _node {
  char data;
  struct node *next;
} Node;

void addFirst(Node **head, char value);
void printList(Node *head);

int main(void) {
  Node *head = NULL;
  addFirst(&head,'H');
  addFirst(&head,'E');
  addFirst(&head,'L');
  addFirst(&head,'P');
  printList(head);
  return 0;
}

void addFirst(Node **head, char value){
    //create a new node
    Node *newNode = malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = *head;
    
    *head = newNode;
}

void printList(Node *head)
{
    Node *temp = head;
    while(temp != NULL)
    {
         printf("%c->", temp->data);
         temp = temp->next;
    }
    printf("NULL\n");
}

`P->L->E->H->NULL`

### addLast

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

typedef struct _node {
  char data;
  struct node *next;
} Node;

void addLast(Node **head, char value);
void printList(Node *head);

int main(void) {
  Node *head = NULL;
  addLast(&head, 'H');
  addLast(&head, 'E');
  addLast(&head, 'L');
  addLast(&head, 'P');
  printList(head);
  return 0;
}

void addLast(Node **head, char value) {
  Node *newNode = malloc(sizeof(Node));
  newNode->data = value;
  newNode->next = NULL;

  if(*head == NULL)
    *head = newNode;
  else{
    Node *lastNode = *head;
    while(lastNode->next != NULL){
      lastNode = lastNode->next;
    }
    lastNode->next = newNode;
  }
}

void printList(Node *head)
{
    Node *temp = head;
    while(temp != NULL)
    {
         printf("%c->", temp->data);
         temp = temp->next;
    }
    printf("NULL\n");
}

`H->E->L->P->NULL`

先打住一下，拆解Linus 的 Good taste

---

## Good taste

[Linked lists, pointer tricks and good taste](https://github.com/mkirchner/linked-list-good-taste)

**data structure**

struct IntListItem{
    int value;
    struct IntListItem *next;
}
typedef struct IntListItem IntListItem;

struct IntList{
    IntListItem *head;
}
typedef struct IntList IntList;

建立一個IntListItem的結構，
該結構含有一個**整數型態的value**，以及**指向IntListItem的指標\*next**

**API**

void remove_cs101(IntList *l, IntListItem *target);
void remove_elegant(IntList *l, IntListItem *target);


### remove_cs101

void remove_cs101(IntList *l, IntListItem *target){
    IntListItem *cur = l->head, *prev = NULL;
    while(cur != target){
        prev = cur;
        cur = cur->next;
    }
    if(prev){
        prev->next = cur->next;
    }else{
        l->head = cur->next;
    }
}

建立兩個指標\*cur, \*prev，其指向的類型皆為IntListItem
\*cur被賦予`l->head` ; \*pre被賦予`NULL`

我的理解為先把while跟if，兩段分開看
**--while--**
* \*l指標變數為指向IntList，而IntList的成員指標變數\*head指向IntListItem(圖1)
簡言之，假設A struct被建立，我們則利用建立的\*head去指向A struct(圖2)
圖1
圖2

* 再把指向 A struct的\*head指標的位址**賦予**給新指標\*cur
所以目前A struct就會被兩個指標變數(\*head, \*cur)所指著(圖3)
圖3

* while就利用cur指標去尋找有無符合target指標
只要都沒符合，就會一路一直找下去
讓**prev位址被賦予cur位址**，而**cur位址被賦予cur的next位址**
直到找到，就離開while迴圈

**--if--**
* 問題就從這出現分支
一為target串列的**第一個node**(節點)就是欲找目標(target)
二為在target串列中的**任意一個**(非第一個)
其實可以往回看，發現`*prev = NULL`這個變數宣告

* 如果為第一個，則不進去while迴圈，直接進入if的else條件
因**欲刪除第一個node**，故需要將head指向`cur->next`

* 如果不為第一個，`cur != target`條件成立，找到則離開while
進入`if(prev)`，因為不為第一個，故prev指標必存在
則**欲刪除該node**，將該node的前一個node指向的Next改為cur的next`prev->next = cur->next`

### remove_elegant
優化remove_cs101的程式

void remove_elegant(IntList *l, IntListItem *target){
    IntListItem **p = &l->head
    while((*p) != target){
        p = &(*p)->next;
    }
    *p = target->next;
}

* 可以觀察到使用指標變數的數量少了，僅需要一個\*\*p

* 指向的位置也有所不同，利用指標的指標(\*\*p)去存取\*head位址

原文:
The code uses an indirect pointer p that holds the address of a pointer to a list item, starting with the address of head.
我:程式碼使用間接指標p，持有(hold)一個到list item指標的位址
我:從head的位址開始

In every iteration, that pointer is advanced to hold the address of the pointer to the next list item, i.e. the address of the next element in the current IntListItem. 
我:在每個迭代(iteration)，該指標進一步地持有(hold)這個到下一個list item的指標位址
我:舉例,下一個元素(element)的位址在當前的IntListItem

When the pointer to the list item (*p) equals target, we exit the search loop and remove the item from the list.
我:當該指標(*p)到list item，會相當於target
我:我們會從該list離開尋找迴圈，以及移除該item

**How does it work?**

The key insight is that using an indirect pointer p has two conceptual benefits:

1.It allows us to interpret the linked list in a way that makes the head pointer an integral part the data structure.
This eliminates the need for a special case to remove the first item.

2.It also allows us to evaluate the condition of the while loop without having to let go of the pointer that points to target.
This allows us to modify the pointer that points to target and to get away with a single iterator as opposed to prev and cur.

Let's look each of these points in turn.