🔏 Linked List

: a set of ordered items. A node consists of data and link, and the link connects nodes.

• Size is not limited
• Insertion and deletion are efficient

⚙ Operations in list

Object : a group of ݊n ordered elements
pos : index in list

▪ add_last(list, item): Add ‘item’ to the end.
▪ add_first(list, item): Add ‘item’ to the beginning.
▪ add(list, pos, item): Add ‘item’ to ‘pos’.
▪ delete(list, pos): Removes the element at ‘pos’.
▪ clear(list): Removes all elements of the list.
▪ replace(list, pos, item): Replace the element at ‘pos’ with ‘item’.
▪ is_in_list(list, item): Check to see if ‘item’ is in the list.
▪ get_entry(list, pos): Return the element at ‘pos’.
▪ Get_length(list): Return the length of the list.
▪ Is_empty(list): Check if the list is empty.
▪ Is_full(list): Check if the list is full.
▪ Display(list): Display all elements in the list.

structure of List

Node consists of entry and address

• Data field (entry) - store the data value (element)
• Link field (address) - stores the address (pointer) of next node

❔ Head pointer : Variable that points to the first node in the list

▶ A node is created by allocating dynamic memory whenever necessary

🔬 application in code using array

🔴 simple Linked List

• Link the data using one link field
• The value of the last node's link is NULL.

📥 Simple Linked List: Insertion

📤 Simple Linked List: Deletion

🔬 Simple Linked List Implementation

: each node in Linked list can be defined using a structure

• ListNode = data + link(pointer)
  

• Node generation: using 'malloc' function

• Setting data fields and link fields
  

• Creating a second node and connecting it to the first node
  

Insertion function

: Since the head pointer changes inside the function, we need a
pointer to the head pointer.

🚩 insert in the middle of list
If ‘*phead’ is not NULL, insert in the middle of list

(1) Copy ‘p’->link to ‘new_node’->link.
(2) Let p -> link point to new_node.

🔬 code

// phead: pointer to the head pointer of the list
// p: preceding node
// new_node: node to be inserted
void insert_node(ListNode **phead, ListNode *p, ListNode *new_node)
{
if( *phead == NULL ){
new_node->link = NULL;
*phead = new_node;
}
else {
if(p == NULL){
printf(“The preceding node cannot be NULL.\n”);
exit(1);
}
else{
new_node->link = p->link;
p->link = new_node;
}
}
}

Deletion function

: The link of ‘p’ is changed to point to the next node of ‘removed’.
so change p.link --> removed.list
(since removed.link = address of next node of ‘removed’)

🔬 code

// phead : pointer to the head pointer
// p: preceding node to be deleted
// removed: node to be deleted
void remove_node(ListNode **phead, ListNode *p, ListNode *removed)
{
if( *phead == NULL ){
printf(“The list is blank.\n”);
}
else {
if( p == NULL )
printf(“The preceding node cannot be NULL.\n”);
else {
p->link = removed->link;
free(removed);
}
}
}

📥📝🗓🖇
⚜🔰🔬🔭▶➡α
✒📤🧾📜📗📕📘💡💾⛏🛠🔑🔏🔊🌈🔥🚩💫❓❗🔰♻✅✔🟥🟧🟨🟩🟦🟪🔺🖼🎞🎨🎗🔑⚠❔🔀↪➰💱🔴🔴🟠🟡🟢🔵🟣🟤⚫🗨🗝🔑🔨🔐🛠🎬🕯📸🔖👾👻✔👑💎🔭🔎