🔏 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 apointer 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);
}
}
}

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