Linked Lists Vocabulary

What is a Linked List?

• Think of a linked list as a treasure hunt where each clue (node) contains a piece of treasure (data) and a pointer to the next clue.

• Unlike arrays, which are like a bookshelf with fixed slots, linked lists are dynamic. You can add or remove clues (nodes) as needed during the treasure hunt.

• Each clue (node) has two parts: the treasure (data) and the address of the next clue (next pointer).

• Linked lists are versatile, like building blocks for more complex structures like stacks, queues, and hash maps.

• The head node is where the treasure hunt begins, pointing to the first clue.

• Node components:

  • Data: treasure in the clue.

  • Next pointer: address of the next clue.

• The last clue (tail node) points to null, indicating the end of the treasure hunt.

Linked Lists vs. Arrays

• Arrays:

  • Like a bookshelf: fixed size defined when you set it up.

  • Holds similar books (data types).

• Linked Lists:

  • Like a treasure hunt: dynamic, add or remove clues (nodes) as you go.

  • Can hold clues (nodes) with different types of treasure (data types).

Types of Linked Lists

• Singly Linked Lists

• Doubly Linked Lists

• Circular Linked Lists

Singly Linked Lists

• Each clue has:

  • Treasure (data).

  • Address of the next clue.

• Traversal is like following a one-way street; you can only go in one direction.

Doubly Linked Lists

• Each clue has:

  • Treasure (data).

  • Address of the previous clue.

  • Address of the next clue.

• Traversal is like a two-way street; you can go forward or backward.

Circular Linked Lists

• Like a carousel, can be singly or doubly linked.

• The last clue points back to the first, creating a continuous loop until you decide to stop.

Basic Operations in Linked Lists

• Performed on Singly Linked Lists:

  • Insertion: Adds a new clue at the beginning of the treasure hunt.

  • Deletion: Removes a clue from the beginning of the treasure hunt.

  • Display: Shows the complete list of clues and treasure.

  • Search: Finds a specific treasure using a key.

  • Delete: Removes a clue using a given key.

Linked List - Insertion Operation:

• Like adding a new clue between two existing clues.

• Example: Inserting clue B between clue A and clue C:

  • Make B point to C: NewNode.next -> RightNode

  • Make A point to B: LeftNode.next -> NewNode

Insertion Types

• Insertion at Beginning

• Insertion at Ending

• Insertion at a Given Position

Insertion at Beginning

• Algorithm:

  1. START

  2. Create a new clue to store the treasure.

  3. Check if the treasure hunt is empty.

  4. If empty, add treasure to the clue and start the hunt with this clue.

  5. If not empty, add treasure to the new clue, link it to the current head, and make this the new starting clue.

  6. END

• Example C Implementation:

struct node {
    int data;
    struct node *next;
  };

  struct node *head = NULL;
  struct node *current = NULL;

  void insertatbegin(int data) {
    struct node *lk = (struct node*) malloc(sizeof(struct node));
    lk->data = data;
    lk->next = head;
    head = lk;
  }

Insertion at Ending

• Algorithm:

  1. START

  2. Create a new clue and assign the treasure.

  3. Find the last clue.

  4. Point the last clue to the new clue.

  5. END

• Example C Implementation:

void insertatend(int data){
    struct node *lk = (struct node*) malloc(sizeof(struct node));
    lk->data = data;
    struct node *linkedlist = head;
    while(linkedlist->next != NULL)
      linkedlist = linkedlist->next;
    linkedlist->next = lk;
  }

Insertion at a Given Position

• Algorithm:

  1. START

  2. Create a new clue and assign treasure to it.

  3. Iterate until the clue at the desired position is found.

  4. Point the new clue to the appropriate next clue.

  5. END

• Example C Implementation:

void insertafternode(struct node *list, int data){
    struct node *lk = (struct node*) malloc(sizeof(struct node));
    lk->data = data;
    lk->next = list->next;
    list->next = lk;
  }

Linked List - Deletion Operation

• Like removing a clue from the treasure hunt.

• Make the next pointer of the clue before the target point to the clue after the target.

  • LeftNode.next -> TargetNode.next

• Disconnect the target clue:

  • TargetNode.next -> NULL

• The deleted clue can be either kept or discarded.

Deletion Types

• Deletion at Beginning

• Deletion at Ending

• Deletion at a Given Position

Deletion at Beginning

• Algorithm:

  1. START

  2. Assign the head pointer to the next clue in the list.

  3. END

• Example C Implementation:

void deleteatbegin(){
    head = head->next;
  }

Deletion at Ending

• Algorithm:

  1. START

  2. Iterate until the second-to-last element is found.

  3. Assign NULL to the next pointer of the second-to-last element.

  4. END

• Example C Implementation:

void deleteatend(){
    struct node *linkedlist = head;
    while (linkedlist->next->next != NULL)
      linkedlist = linkedlist->next;
    linkedlist->next = NULL;
  }

Deletion at a Given Position

• Algorithm:

  1. START

  2. Iterate until the target clue at the specified position is found.

  3. Assign the next pointer of the previous clue to the next pointer of the current clue.

  4. END

• Example C Implementation:

void deletenode(int key){
    struct node *temp = head, *prev;
    if (temp != NULL && temp->data == key) {
      head = temp->next;
      return;
    }
    while (temp != NULL && temp->data != key) {
      prev = temp;
      temp = temp->next;
    }
    if (temp == NULL) return;
    prev->next = temp->next;
  }

Linked List - Reversal Operation

• Like flipping the entire treasure hunt, making the last clue the new starting point.

  1. START

  2. Use three pointers: prev, next, and head.

  3. Point the current clue to head and assign its next value to the prev clue.

  4. Iteratively repeat step 3 for all clues.

  5. Assign head to the prev clue.

• Algorithm:

• Example C Implementation:

void reverseList(struct node** head){
    struct node *prev = NULL, *cur=*head, *tmp;
    while(cur!= NULL) {
      tmp = cur->next;
      cur->next = prev;
      prev = cur;
      cur = tmp;
    }
    *head = prev;
  }

Linked List - Search Operation

• Finding a specific treasure by comparing each clue's treasure to the key.

• Algorithm:

  1. START

  2. If the treasure hunt is not empty, iteratively check if the list contains the key.

  3. If the key element is not present in the list, the search is unsuccessful.

  4. END

• Example C Implementation:

int searchlist(int key){
    struct node *temp = head;
    while(temp != NULL) {
      if (temp->data == key) {
        return 1;
      }
      temp=temp->next;
    }
    return 0;
  }

Linked List - Traversal Operation

• Walking through all clues in order and showing the treasure in each.

• Algorithm:

  1. START

  2. While the treasure hunt is not empty and the end is not reached, print the data in each clue.

  3. END

• Example C Implementation:

```c
void printList(){
struct node *p = head;
printf("\n[");
while(p != NULL) {
printf("