linked-list-101

Table of Content

1. Basics
   • Definitions
   • Accessing Data
   • Linking Data
   • Freeing Memory
2. Types of Linked List
3. Operations of Linked List
   • Push Head
   • Push at Index
   • Push Tail
   • Alternative Push Tail
   • Pull Head
   • Pull Tail
   • Pull at Index
   • Printing Lists

Perquisites

• Data Types
• Input/Output
• Functions
• Struct

Basics

requires malloc.h

#include<malloc.h> //OR
#include<stdlib.h>

Definitions

Data Type Declaration

​ A Node is a structure of variables that contains

• Data - can be integers/array/pointers/another structs
• Pointer - that points to another Node

typedef struct Node{
    int main;
    struct Node* next;
} Node;

Struct Definition

​ Nodes are defined via the malloc functions

// var = (dataType)malloc(size);
head_node = (Node*)malloc(sizeof(Node));

​ Nodes can be defined globally

Node* head_node = (Node*)malloc(sizeof(Node));

int main(){
}

​ Whereas when this is when Nodes are defined locally.

int main(){
 Node* head_node = (Node*)malloc(sizeof(Node));
    Node* second_node;
    
    second_node = (Node*)malloc(sizeof(Node));
}

Accessing Data

​ The -> operators allows pointing the data of which the struct is pointed at. ex:

int main(){
    Node* head_node;
    head_node = (Node*)malloc(sizeof(Node));
     
    head_node->data = 3;
     // is equal to
    (*head_node).data = 3;
     // the expression above allows 
     // accessing data on which the pointer is 
     // pointed at. (value of head_node)
}

Linking Data

​ The pointer *link has to be accessed and linked to another Node using -> operator. ex:

int main(){
    Node* head_node,second_node);
    
    head_node = (Node*)malloc(sizeof(Node));
    second_node = (Node*)malloc(sizeof(Node));
    
    head_node->data = 3;
    head_node->next = second_node;
     // next pointer points to second_node
     // *next is the second_node
    second_node->data = 5;
    second_node->next = NULL;
     // if this is the end of the link
     // NULL assignment is requried
}

​ Both of these prints the same value, since they are linked and can be accessed from head.

printf("%d", second_node->data);

printf("%d", head_node->next->data);

Freeing Memory

​ There is no garbage collection in C thus, memory of pointers need to be free otherwise they will stick until computer is restarted.

free(node);
node=NULL;

​ It is good practise to assign NULL after freeing the node as it prevent you from accidentally trying to access the freed memory

Types of Linked List

There are several types of linked list that can exist. It all depends on how they are linked list. For Example:

• Singly Linked List - are linked with only the next pointer. Hence they are only capable of being processed one way

typedef struct Node{
    char name[30];
    struct Node* next;
}Node;

• Doubly Linked List - are linked with next pointer and prev pointer, indicating the next and previous node such that it is possible to go through the list both way.

typedef struct Node{
    char name[30];
    struct Node* next;
    struct Node* prev;
}Node;

• Circular Linked List - can be singly or doubly, are list that goes around when it meets the end. Instead of NULL, it points back to *head pointer.

Other than head pointer, tail pointer can also be defined to point at the end. More discussed at [tail pointers](#Tail Pointers)

Operations of Linked List

​ Lists of operations that are commonly found in linked lists

• Adding Element
  • Push Head
  • Insert
  • Push Tail
• Deleting Element
  • Pull Tail
  • Pull Middle
  • Pull Head
• Printing List

Handling functions with linked lists

​ Single pointer is needed if we only want to point to it’s list as we only have reference from the head of the list.

void editValue(Node* head, int new_value){
    head->data = new_value;
}

int main(){
    Node* head = (Node*)malloc(sizeof(Node));
    // ...
    head->data = 5;
    editValue(head, 10);
    // ...
}

​ Double pointer is needed if we need to modify the pointer of the reference.

void editNode(Node* *head, int new_value){
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->data = new_value;
        new_node->next = NULL;
    *head=new_node;
}
int main(){
    // ...
    Node* head = (Node*)malloc(sizeof(Node));-
    head->data = 5;
    editNode(&head, 10);
    // ...
}

​ However if we used global variable, we wouldn’t need to pass the Node* pointer to the function

Node* head = (Node*)malloc(sizeof(Node));

void editNode(int new_value){
        Node* new_node = (Node*)malloc(sizeof(Node));
        new_node->data = new_value;
        new_ndoe->next = NULL;
    head = new_node;
}
int main(){
    //...
    head->data = 5;
    editNode(10);
    //...
}

1. Push Head (Simplest)

Adding element to the front of the list and linking the head to the new node

Code:

        void pushHead(int new_value){
            Node* new_node = (Node*)malloc(sizeof(Node));
            new_node->data = new_value;
            new_node->next = head;
            head = new_node;
        }

Processes:

1. Creating New Node to hold the new data

2. Linking New Node to where head is pointing

3. Assign the head to the New Node so that the node become the new head.

Function Calling:

    pushHead("Joyce Byers");
    pushHead("Jim Hopper");
    pushHead("Mike Wheeler");
    pushHead("Eleven");
    pushHead("Dustin Henderson");
    pushHead("Lucas Sinclair");
    pushHead("Nancy Wheeler");

Illustration:

Notice how the names are added to the first of the list.

2. Push at Index

Inserting at middle is divided into two. Elements can be inserted by index, or they can be automatically sorted by what’s called priority queue. This also works when it tries to add to the last

Code:

        void insertAt(int index, char* new_name){
            Node* rover = head;
            for( int i=0 ; i<index-1 ; i++ ){
                rover = rover->next;
            }
            Node* new_node = (Node*)malloc(sizeof(Node));
             strcpy(new_node->name, new_name);
             new_node->next = rover->next;
            rover->next=new_node;
        }

Processes:

1. Create a new node called rover and points it to head
2. Move where the rover is pointing to the next node until it is pointing at just before index
3. Create a new node to hold new data and assign link new node to next of rover
4. Set the next node of the rover to this new node.

Warning:

​ The program will actually break when you try to add elements that are out of index. Hence a little if is needed to prevent that from happening

            for( int i=0 ; i<index-1 ; i++ ){
                if(rover!=NULL){
                    rover = rover->next; 
                }else{
                    printf("\nIndex is out of Bound!");
                    delay(1);
                    return;
                }
            }

Function Calling:

// at middle of the list
    insertAt(3, "Mimus polyglottos");
// index is out of bound
    insertAt(10, "Citrullus lanatus");
// at the last of the list
    insertAt(7, "Averrhoa carambola");

Illustration:

3. Push Tail (Slow Method)

​ Deleting an element at the end can be done either by loop (slow) or by having an end pointer

Code:

First way of doing it by looping rover until right before the end (indicated by the next pointer of rover is NULL).

void pushTail(char* new_value){
    Node* rover = head;
    while(rover->next != NULL){
        rover = rover->next;
    }
    Node* new_node = (Node*)malloc(sizeof(Node));
    strcpy(new_node->name , new_value);
    new_node->next = NULL;
    rover->next = new_node;
} 

Processes:

1. Create a rover and move it until the end (right before NULL)
2. Create a new node and assign its value, also its next pointer pointing at NULL
3. Assign the next pointer of Rover to be the new Node

Function Calling:

            pushTail("Discord");
            pushTail("Twitch");
            pushTail("Instagram");
            pushTail("Line");

Illustration:

Tail Pointers

​ Alternatively, a tail pointer can be used to point the tail of the list such that new nodes can be added directly to the tail.

Node* head = NULL;
Node* tail = NULL;

However, adding tail nodes require changes to the function to assign the new tail node whenever new tail is created.

For example: [pushHead](#Push Head (Simplest))

 // singly linked list
void pushHead(char* new_name){
    Node* new_node = (Node*)malloc(sizeof(Node));  
    strcpy(new_node->name, new_name);              
    new_node->next = head;
    head = new_node;
}
 // doubly linked list
void pushHeadDoubly(char* new_name){
    Node* new_node = (Node*)malloc(sizeof(Node));  
    strcpy(new_node->name, new_name);              
    new_node->next = head;
    head = new_node;
     // for which list has one and only item.
    if(head->next == NULL){ 
        tail = new_node;
    }
}

4. Push Tail (No looping)(Simpler)

​ Alternatively, simpler push tail can be done by adding element on the tail pointer.

Code:

void pushTail2(char* new_value){
    Node* new_node = (Node*)malloc(sizeof(Node));
    strcpy(new_node->name, new_value);
    new_node->next = NULL;
    
    tail->next = new_node;
    tail = new_node;
}

Processes:

1. Create new node and assign new node with new values
2. Set the next pointer of new node to point at NULL
3. Set the next pointer of the tail node to be the new node
4. Update the tail of the list to be the new node.

Calling Function:

​ Same as the one in [Push Tail](#Push Tail (Slow Method))

Illustration:

5. Pull Head

Code:

    void pullHead(){
        // to prevent trying to pull in an empty list
        if(head!=NULL){
            Node* temp = head;
            // checking if list only have one node
            if(head->next!=NULL){
                head=head->next;
            }else{
                head=NULL;
                tail=NULL;
            }
            free(temp);
            temp = NULL;
        }
    }

Processes:

1. Check if list contains a node, if true, then create a temporary node pointing to the head
2. Check if list contains more than one node, if true, move head to the next node. else, assign NULL to head and assign NULL to tail, such that the list is empty.
3. Free the memory used for temp

Illustration:

6. Pull Tail

​ Deleting an element of the end is not possible without looping from the start except if doubly linked list is implemented. We need to link the previous node to NULL however we have no prev pointer

Code:

    void pullTail(){
        // prevent trying to delete in an empty list
        if(head != NULL){
            // check if it only have one node
            if(head->next == NULL){
                free(head);
                head = NULL;
                tail = NULL;
            }else{
                Node* rover = head;
                while(rover->next->next != NULL){
                    rover = rover->next;
                }
                free(rover->next);
                rover->next = NULL;
                tail = rover;
            }
        }
    }

Processes:

1. Check if list is empty, if not, check if list only have one node.
   If node only have one node, then free memory used of that node and assign head and tail pointer to NULL.
2. If it have more than one element, rover until it points just before the last node. (second last)
3. Free memory used by node next to rover and set the next pointer of rover to NULL. (rover become the last node in list)
4. (if tail pointer exist) Assign the tail pointer to point at the rover (last node)

Illustration:

7. Pull at Index

​ Pulling at index is somewhat similar to [pull tail](#Pull Tail) but instead of roving until the end, we rove until the node right before index and if user want to pull at first index, we would just call [pull head](#Pull Head)

Code:

void _pullAt(int index){
    // check to prevent trying to delete on empty list
    if(rover!=NULL){
        if(index==0){
            Node* temp = head;
            if(head->next!=NULL){
                head=head->next;
            }else{
                head=NULL;
                tail=NULL;
            }
            free(&temp);
            temp = NULL;
            // or the same as pullHead();
        }else{
            Node* rover = head;
            for(int i=0; i<index-1; i++){
                if(rover==NULL){
                    rover = rover->next;
                }else{
                    printf("\nIndex out of bound!");delay(1);
                    return;
                }
            }
            free(rover->next);
            rover->next = rover->next->next;
            if(rover->next == NULL){
                tail = rover;
            }
        }
    }
}

Processes:

1. Check if list is empty, if not, check if list only have one node.
   If node only have one node, then free memory used of that node and assign head and tail pointer to NULL. (same as pull head)
2. If it have more than one element, rover until it points just before the node at index.
3. Free memory used of node pointed by rover and set the next pointer of rover to NULL. (rover become the last node in list)
4. (if tail pointer exist) Assign the tail pointer to point at the rover (last node)

Illustration:

More Operation

8. Printing Lists

​ Printing list of nodes is easy. It uses the methods mentioned above.

Code:

void screen1(){
    Node* traverse = head;
    for( int i=0 ; traverse != NULL ; i++){
        printf("%s\n",i+1,traverse->name);
        traverse = traverse->next;
    }
}

Processes:

1. Create a temporary node to traverse (the same as rover node)
2. While looping through the next nodes, prints as it goes.

Additional:

• Additional Headings and Closings can be added to make the menu more approachable

void screen1(){
    Node* traverse = head;
    printf("----Social Medias----\n");
    for( int i=0 ; traverse != NULL ; i++){
        printf("%d. %s\n",i+1,traverse->name);
        traverse = traverse->next;
    }
    printf("---------------------\n");
    printHeadTail();
}

• Head pointer and Tail Pointer can be printed to indicate what head pointer and tail pointer is pointing at

void printHeadTail(){
    if(head!=NULL) printf("head: %s\n",head->name);
    else printf("head: NULL\n");
    if(tail!=NULL) printf("tail: %s\n",tail->name);
    else printf("head: NULL\n");
}