linked lists

** Basic Linked List Operations:**

1. Insertion:

   • Insert at the Beginning
   • Insert at the End
   • Insert after a Given Node

2. Deletion:

   • Delete at the Beginning
   • Delete at the End
   • Delete a Specific Node

3. Traversal: Traverse the linked list to access and print its elements.

4. Search: Find a specific element in the linked list.

Now, let's go through examples of these basic linked list operations in C, Python, and JavaScript.

Below are the nodes we will be using for these operations:

Certainly! Here are the node implementations in C, Python, and JavaScript along with the linked list operations using these nodes.

Node Implementations:

1. C:

1
2struct Node {
3    int data;
4    struct Node* next;
5};
6

2. Python:

1
2class Node:
3    def __init__(self, data):
4        self.data = data
5        self.next = None

3. JavaScript:

1
2class Node {
3    constructor(data) {
4        this.data = data;
5        this.next = null;
6    }
7}
8

Let's go through the basic linked list operations in detail, with explanations and examples in C, Python, and JavaScript.

Linked List Operations:

1. Insertion at the Beginning:

This operation involves adding a new node at the beginning of the linked list.

• Explanation:

  • Create a new node with the given data.
  • Make the new node's next point to the current head.
  • Update the head to point to the new node.

• Example in C:

1
2struct Node* insertAtBeginning(struct Node* head, int newData) {
3    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
4    newNode->data = newData;
5    newNode->next = head;
6    return newNode;
7}
8

• Example in Python:

1
2def insertAtBeginning(head, newData):
3    newNode = Node(newData)
4    newNode.next = head
5    return newNode

• Example in JavaScript:

1
2function insertAtBeginning(head, newData) {
3    const newNode = new Node(newData);
4    newNode.next = head;
5    return newNode;
6}
7

2. Insertion at the End:

This operation involves adding a new node at the end of the linked list.

• Explanation:

  • Create a new node with the given data.
  • If the list is empty, make the new node the head.
  • Otherwise, traverse to the last node and make its next point to the new node.

• Example in C:

1
2struct Node* insertAtEnd(struct Node* head, int newData) {
3    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
4    newNode->data = newData;
5    newNode->next = NULL;
6
7    if (head == NULL) {
8        return newNode;
9    }
10
11    struct Node* current = head;
12    while (current->next != NULL) {
13        current = current->next;
14    }
15    current->next = newNode;
16    return head;
17}
18

• Example in Python:

1
2def insertAtEnd(head, newData):
3    newNode = Node(newData)
4    if head is None:
5        return newNode
6
7    current = head
8    while current.next:
9        current = current.next
10    current.next = newNode
11    return head

• Example in JavaScript:

1
2function insertAtEnd(head, newData) {
3    const newNode = new Node(newData);
4    if (!head) {
5        return newNode;
6    }
7
8    let current = head;
9    while (current.next) {
10        current = current.next;
11    }
12    current.next = newNode;
13    return head;
14}
15

3. Insertion after a Given Node:

This operation involves adding a new node after a specific node in the linked list.

• Explanation:

  • Check if the previous node exists.
  • Create a new node with the given data.
  • Make the new node's next point to the next node of the previous node.
  • Update the previous node's next to point to the new node.

• Example in C:

1
2void insertAfterNode(struct Node* prevNode, int newData) {
3    if (prevNode == NULL) {
4        printf("Previous node cannot be NULL\n");
5        return;
6    }
7
8    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
9    newNode->data = newData;
10    newNode->next = prevNode->next;
11    prevNode->next = newNode;
12}
13

• Example in Python:

1
2def insertAfterNode(prevNode, newData):
3    if prevNode is None:
4        print("Previous node cannot be None")
5        return
6    
7    newNode = Node(newData)
8    newNode.next = prevNode.next
9    prevNode.next = newNode

• Example in JavaScript:

1
2function insertAfterNode(prevNode, newData) {
3    if (!prevNode) {
4        console.log("Previous node cannot be null");
5        return;
6    }
7
8    const newNode = new Node(newData);
9    newNode.next = prevNode.next;
10    prevNode.next = newNode;
11}
12

4. Deletion at the Beginning:

This operation involves removing the first node from the linked list.

• Explanation:

  • Check if the list is empty.
  • Store the current head in a temporary variable.
  • Update the head to point to the second node.
  • Free the memory of the removed node.

• Example in C:

1
2struct Node* deleteAtBeginning(struct Node* head) {
3    if (head == NULL) {
4        printf("List is empty\n");
5        return NULL;
6    }
7
8    struct Node* temp = head;
9    head = temp->next;
10    free(temp);
11    return head;
12}
13

• Example in Python:

1
2def deleteAtBeginning(head):
3    if head is None:
4        print("List
5
6 is empty")
7        return None
8    temp = head
9    head = temp.next
10    temp.next = None
11    return head

• Example in JavaScript:

1
2function deleteAtBeginning(head) {
3    if (!head) {
4        console.log("List is empty");
5        return null;
6    }
7    const temp = head;
8    head = temp.next;
9    temp.next = null;
10    return head;
11}
12

5. Deletion at the End:

This operation involves removing the last node from the linked list.

• Explanation:

  • Check if the list is empty.
  • If the list has only one node, set the head to null.
  • Traverse to the second-to-last node and update its next to null.
  • Free the memory of the removed node.

• Example in C:

1
2struct Node* deleteAtEnd(struct Node* head) {
3    if (head == NULL) {
4        printf("List is empty\n");
5        return NULL;
6    }
7
8    if (head->next == NULL) {
9        free(head);
10        return NULL;
11    }
12
13    struct Node* current = head;
14    while (current->next->next != NULL) {
15        current = current->next;
16    }
17    free(current->next);
18    current->next = NULL;
19    return head;
20}
21

• Example in Python:

1
2def deleteAtEnd(head):
3    if head is None:
4        print("List is empty")
5        return None
6    if head.next is None:
7        head = None
8        return None
9    current = head
10    while current.next.next:
11        current = current.next
12    current.next = None
13    return head

• Example in JavaScript:

1
2function deleteAtEnd(head) {
3    if (!head) {
4        console.log("List is empty");
5        return null;
6    }
7    if (!head.next) {
8        head = null;
9        return null;
10    }
11    let current = head;
12    while (current.next.next) {
13        current = current.next;
14    }
15    current.next = null;
16    return head;
17}
18

6. Deletion of a Specific Node:

This operation involves removing a node with a specific value from the linked list.

• Explanation:

  • Check if the list is empty.
  • If the node to be deleted is the head, update the head.
  • Traverse the list and find the node before the target node.
  • Update the previous node's next to skip the target node.
  • Free the memory of the target node.

• Example in C:

1
2struct Node* deleteNode(struct Node* head, int key) {
3    if (head == NULL) {
4        printf("List is empty\n");
5        return NULL;
6    }
7
8    if (head->data == key) {
9        struct Node* temp = head;
10        head = temp->next;
11        free(temp);
12        return head;
13    }
14
15    struct Node* current = head;
16    struct Node* prev = NULL;
17    while (current != NULL && current->data != key) {
18        prev = current;
19        current = current->next;
20    }
21
22    if (current == NULL) {
23        printf("Node with key %d not found\n", key);
24        return head;
25    }
26
27    prev->next = current->next;
28    free(current);
29    return head;
30}
31

• Example in Python:

1
2def deleteNode(head, key):
3    if head is None:
4        print("List is empty")
5        return None
6    if head.data == key:
7        temp = head
8        head = temp.next
9        temp.next = None
10        return head
11
12    current = head
13    prev = None
14    while current and current.data != key:
15        prev = current
16        current = current.next
17    if current is None:
18        print("Node with key", key, "not found")
19        return head
20
21    prev.next = current.next
22    current.next = None
23    return head

• Example in JavaScript:

1
2function deleteNode(head, key) {
3    if (!head) {
4        console.log("List is empty");
5        return null;
6    }
7    if (head.data === key) {
8        const temp = head;
9        head = temp.next;
10        temp.next = null;
11        return head;
12    }
13
14    let current = head;
15    let prev = null;
16    while (current && current.data !== key) {
17        prev = current;
18        current = current.next;
19    }
20    if (current === null) {
21        console.log("Node with key", key, "not found");
22        return head;
23    }
24
25    prev.next = current.next;
26    current.next = null;
27    return head;
28}
29

These are some of the basic linked list operations explained with examples in C, Python, and JavaScript. Linked lists are fundamental data structures that form the basis for more complex structures like stacks, queues, and graphs.