CS Code

Coding, quiz & more

In this tutorial, we are going to learn the Linked List operations and implementation of Linked List in C, C++, Java, Python.

Linked List is a linear data structure in which nodes are connected to each other. Each node stores the address of next node.

Check basic concepts of Linked List here.

Structure of node in Linked List is

``````struct Node
{
int data;
struct Node* next;
}; ``````

Note: If next pointer of a node is set to `NULL` then its end of the linked list.

• Insert
• Insert At Start
• Insert At End
• Insert At Position
• Delete
• Delete At Start
• Delete At End
• Delete At Position
• Traverse : Traversing means visiting every node of the linked list at once.

## Insert Operation

#### Insert At Start:

• Allocate memory for new node using malloc()
• Store data in the node
• Change next pointer of new node to point to head
• Change head to point to newly created node
``````struct node *newNode;   //refer above struct node
newNode = malloc(sizeof(struct node));
newNode->data = 5;
``````

#### Insert At End:

• Allocate memory for new node using malloc()
• Store data in the node
• Traverse to the last node
• Change next pointer of last node to newly created node
• Set next pointer of newly created node to `NULL`
``````struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 5;
newNode->next = NULL;

while(temp->next != NULL){
temp = temp->next;
}

temp->next = newNode;``````

#### Insert At Position:

• Allocate memory for new node using malloc()
• Store data in the node
• Traverse to the node just before the position
• Change the next of newly created node to the node before the position(Like mentioned in the code).
``````struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 5;

//position input by user. Display appropriate error message if position is greater than length of linked list

for(int i=1; i < position; i++) {
if(temp->next != NULL) {
temp = temp->next;
}
}
newNode->next = temp->next;
temp->next = newNode;``````

## Delete Operation

#### Delete At Start

• Store first node in a temporary struct node pointer
• Point head to the second node
• Free the temporary node
``````struct node *temp = head;
free(temp);``````

#### Delete At End

• Traverse to the second last element
• Store next of second last element in temporary struct node pointer
• Change its next pointer to null
• Free the temporary pointer
``````struct node* temp = head;
while(temp->next->next!=NULL){
temp = temp->next;
}
struct node* t = temp->next;
temp->next = NULL;
free(t);``````

#### Delete At Position

• Traverse to the node before the position to be deleted
• Change next pointers as mentioned in code below
``````for(int i=1; i< position; i++) {
if(temp->next!=NULL) {
temp = temp->next;
}
}
temp->next = temp->next->next;``````

Traversing meaning visiting each node in the Linked List at once. Starting from `head` pointer to the last node.

Last node is identified by the next pointer. If next pointer of a node is set to `NULL` then this node is last node of the linked list.

``````struct node *temp = head;

while(temp != NULL)
{
printf("%d  ->  ",temp->data);
temp = temp->next;
}``````

## Implementing Of Linked List Operations

```
#include <stdio.h>
#include <stdlib.h>  //for malloc()

// Create a node
struct Node {
int item;
struct Node* next;
};

void insertAtBeginning(struct Node** ref, int data) {
// Allocate memory to a node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

// insert the item
new_node->item = data;
new_node->next = (*ref);

// Move head to new node
(*ref) = new_node;
}

// Insert a node after a node
void insertAfter(struct Node* node, int data) {
if (node == NULL) {
printf("the given previous node cannot be NULL");
return;
}

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->item = data;
new_node->next = node->next;
node->next = new_node;
}

void insertAtEnd(struct Node** ref, int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *ref;

new_node->item = data;
new_node->next = NULL;

if (*ref == NULL) {
*ref = new_node;
return;
}

while (last->next != NULL)
last = last->next;

last->next = new_node;
return;
}

void deleteNode(struct Node** ref, int key) {
struct Node *temp = *ref, *prev;

if (temp != NULL && temp->item == key) {
*ref = temp->next;
free(temp);
return;
}
// Find the key to be deleted
while (temp != NULL && temp->item != key) {
prev = temp;
temp = temp->next;
}

// If the key is not present
if (temp == NULL) return;

// Remove the node
prev->next = temp->next;

free(temp);
}

void printList(struct Node* node) {
while (node != NULL) {
printf(" %d ", node->item);
node = node->next;
}
}

// Driver program
int main() {

printf("\nAfter deleting an element: ");
}
```
```#include <stdlib.h>
#include <iostream>

using namespace std;

// Create a node
struct Node {
int item;
struct Node* next;
};

void insertAtBeginning(struct Node** ref, int data) {

// Allocate memory to a node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));

// insert the item
new_node->item = data;
new_node->next = (*ref);

// Move head to new node
(*ref) = new_node;
}

// Insert a node after a node
void insertAfter(struct Node* prev_node, int data) {
if (prev_node == NULL) {
cout << "the given previous node cannot be NULL";
return;
}

struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->item = data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}

void insertAtEnd(struct Node** ref, int data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *ref;

new_node->item = data;
new_node->next = NULL;

if (*ref == NULL) {
*ref = new_node;
return;
}

while (last->next != NULL)
last = last->next;

last->next = new_node;
return;
}

void deleteNode(struct Node** ref, int key) {
struct Node *temp = *ref, *prev;

if (temp != NULL && temp->item == key) {
*ref = temp->next;
free(temp);
return;
}
// Find the key to be deleted
while (temp != NULL && temp->item != key) {
prev = temp;
temp = temp->next;
}

// If the key is not present
if (temp == NULL) return;

// Remove the node
prev->next = temp->next;

free(temp);
}

void printList(struct Node* node) {
while (node != NULL) {
cout << node->item << " ";
node = node->next;
}
}

// Driver program
int main() {

cout << "\nAfter deleting an element: ";
}```
```class LinkedList {

// Create a node
class Node {
int item;
Node next;

Node(int d) {
item = d;
next = null;
}
}

public void insertAtBeginning(int data) {
// insert the item
Node new_node = new Node(data);
}

public void insertAfter(Node prev_node, int data) {
if (prev_node == null) {
System.out.println("The given previous node cannot be null");
return;
}
Node new_node = new Node(data);
new_node.next = prev_node.next;
prev_node.next = new_node;
}

public void insertAtEnd(int data) {
Node new_node = new Node(data);

return;
}

new_node.next = null;

while (last.next != null)
last = last.next;

last.next = new_node;
return;
}

void deleteNode(int position) {
return;

if (position == 0) {
return;
}
// Find the key to be deleted
for (int i = 0; node != null && i < position - 1; i++)
node = node.next;

// If the key is not present
if (node == null || node.next == null)
return;

// Remove the node
Node next = node.next.next;

node.next = next;
}

public void printList() {
while (node != null) {
System.out.print(node.item + " ");
node = node.next;
}
}

public static void main(String[] args) {

llist.insertAtEnd(1);
llist.insertAtBeginning(2);
llist.insertAtBeginning(3);
llist.insertAtEnd(4);

llist.printList();

System.out.println("\nAfter deleting an element: ");
llist.deleteNode(3);
llist.printList();
}
}```
```
# Create a node
class Node:
def __init__(self, item):
self.item = item
self.next = None

def __init__(self):

# Insert at the beginning
def insertAtBeginning(self, data):
new_node = Node(data)

# Insert after a node
def insertAfter(self, node, data):

if node is None:
print("The given previous node must inLinkedList.")
return

new_node = Node(data)
new_node.next = node.next
node.next = new_node

# Insert at the end
def insertAtEnd(self, data):
new_node = Node(data)

return

while (last.next):
last = last.next

last.next = new_node

# Deleting a node
def deleteNode(self, position):

return

if position == 0:
temp_node = None
return

# Find the key to be deleted
for i in range(position - 1):
temp_node = temp_node.next
if temp_node is None:
break

# If the key is not present
if temp_node is None:
return

if temp_node.next is None:
return

next = temp_node.next.next
temp_node.next = None
temp_node.next = next

def printList(self):
while (temp_node):
print(str(temp_node.item) + " ", end="")
temp_node = temp_node.next

if __name__ == '__main__':