rakesh kumar

Posted on

# Linked List in Data Structure

## Linked List in Data Structure

There are broadly two types of Data structures: Linear and Non-linear. Linear data structures are those in which every element is connected to the previous element and the elements are present at a single level.

Some examples of linear data structures are- Arrays, linked lists, stack,s and queues. Thus, a linked list is a linear data structure in which elements are not stored contiguously in the memory.

1. A linked list a collection of randomly stored elements in the memory. These elements are called nodes.

2. We use pointers to connect and maintain the linear order between these random data points.

3. Every node of a linked list consists of at least two parts-

Data

Let's see how each node of the linked list is represented. Each node consists:

A data item
We wrap both the data item and the next node reference in a struct as:

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

Understanding the structure of a linked list node is the key to having a grasp on it.

Each struct node has a data item and a pointer to another struct node. Let us create a simple Linked List with three items to understand how this works.

/* Initialize nodes */

``````struct node *head;
struct node *one = NULL;
struct node *two = NULL;
struct node *three = NULL;
``````

/* Allocate memory */

``````one = malloc(sizeof(struct node));
two = malloc(sizeof(struct node));
three = malloc(sizeof(struct node));
``````

/* Assign data values */

``````one->data = 1;
two->data = 2;
three->data=3;
``````

/* Connect nodes */

``````one->next = two;
two->next = three;
three->next = NULL;
``````

If you didn't understand any of the lines above, all you need is a refresher on pointers and structs.

In just a few steps, we have created a simple linked list with three nodes.

The above diagram shows that in a linked list, the elements are not stored contiguously but it appears that they are stored contiguously.

The most important thing in a linked list is the pointer. We need to have a starting pointer (HEAD) to access the linked list. The last node in the linked list has a pointer to NULL.

Properties of linked list in Data Structure

1. The elements of the linked list may or may not be present contiguously in the memory.

2. We need not declare the list size in advance.

3. We can allocate the memory dynamically whenever we need to add more nodes or perform any other operation on the list.

4. The linked list cannot contain an empty node.

5. A node in a linked list is a combination of two data types- a pointer and a primitive data type such as int or float. Therefore, we use structures to implement a linked list.

Applications of Linked List in Data Structure

1. We can implement stack and queue data structures using a linked list.

2. It is used in the implementation of graphs. Example- Adjacency list representation in a graph makes use of a linked list.

3. Symbol table management in compiler design uses a linked list.

4. It is used to prevent collision in hashing.

5. Linked list is used for DMA (Dynamic Memory Allocation).

6. We can use linked lists for performing arithmetic operations on long int.

7. Representation of a sparse tree matrix also requires a linked list.

## Data Structure Linked List vs Array

Let us see a few comparisons between them.

There are certain basic operations that a linked list data structure supports. These operations are:

1. Traversal:
It means visiting each node from the beginning till the end.

2. Insertion:
This operation inserts an element at any given position in the list.

3. Deletion:
Deletion operation helps in deleting a node from the linked list.

4. Display:
This operation is used to print/display all the data elements of the linked list.

5. Search:
search operation helps in searching an element by traversing it.

Declaration and Initialization of a Node in a linked list:
A node is a heterogeneous data type. Therefore, we use a structure to create it.

struct Node
{
int data; //the first part of the node where data is stored
struct node *Next; //Self-referencing structure. It links two nodes.
};
The linked list supports dynamic memory allocation. Therefore, we will use the functions malloc, calloc and realloc for memory allocation.

The code will be:

Ptr = (struct Node *)malloc(sizeof(struct Node *)); //Initializing Ptr
Dynamic memory is allocated inside the heap, which is why we need functions like malloc. Here, malloc will return the address of the node.

Traversal in a Singly Linked List
Traversal means visiting each node of the linked list. Once the node has been created, we can do its traversal in the following way.

``````struct Node *Ptr;
while(Ptr != NULL)
{
Print (Ptr→data);
Ptr = Ptr→Next;
}
``````

The time complexity for the above pseudo-code will be O(n).

When we talk about insertion in a linked list, we take into consideration three different cases:

1. Insertion at the beginning of the list

2. Insertion after a particular node.

3. Insertion at the end of the list

Insertion at the beginning:
Insertion at the beginning means we will insert a node at the front of the list in the following way:

The above diagram shows that we have a linked list of the following elements: 10→20→30.

Once we insert a new node at the beginning, the list will be 50→10→20→30.

Pseudo-code:

``````Void Insert_at_beginning(int key)
{
struct Node *temp; //temp is a pointer pointing to the node to be inserted.
temp = (struct Node*) malloc(sizeof(struct Node));
if(temp != NULL)
{
temp→data = key;   //key is the data value to be inserted
temp→next = Head;  //this step will make the incoming node the first node.
}
}
``````

Insertion after a particular node

We need to traverse all the nodes before the position of insertion of the new node. For doing this, we maintain an additional temporary pointer.

For example, suppose we wish to link all the letters of the word ‘TECHVIDVAN’ and we forgot to add “H”.
We can insert this ‘H’ once the list is created as shown below

In this case, we will have a temporary pointer named ‘temp’. This pointer temp will be pointing to ‘C’ because we need to insert ‘H’ after ‘C’.

The lines of code that will help to do this will be:

``````temp->Next = Ptr->Next;
Ptr->Next = temp;

``````

Insertion at the End:
To insert a node at the end of the list, we first need to traverse the whole list.
The function for insertion at the end is:

``````void Insert_at_end(int key)
{
struct Node *temp, *Ptr;
temp = (struct Node*) malloc(sizeof(struct Node));
if(temp != NULL)
{
temp->data = key;
temp->Next = NULL;
if(Head == NULL) //This will be true if the list is initially empty
{
return;
}
while(Ptr->Next != NULL)
Ptr->Next = temp;
}
}
``````

Just like insertion, deletion also works in three different cases:

1. Deletion from beginning

2. Deletion at the end

3. Deleting a node other than the first and the last node

Deletion from the beginning:
It involves deleting the first node of the linked list.

If we perform deletion of one node at the beginning, the linked list will be:
20→30→40.

The function for performing deletion at the beginning is:

``````void Delete_from_beginning(int key)
{
if(Head == NULL)  //i.e. If the list is empty
{
return;
}
free(Ptr);
}
``````

Whenever we delete a node, we make the memory area occupied by that node free by using the ‘free’ function. Otherwise, it might lead to a memory leakage problem.

Deletion at the end:

For deletion of the last node, we need to make the address of the second last node point to NULL. For doing this, we will make use of an extra pointer named ‘Prev’.

While deleting the last node, we will first free the last node and then make the Next of the second last node as NULL.
The function for deletion at the end will as follows:

``````void Delete_at_end(int key)
{
struct Node *Prev = NULL;
if(Head == NULL)  //If the list is empty
{
return;
}
if(Head->Next == NULL) //If the list has only one element
{
free(Ptr);
}
else
{
while(Ptr->Next != NULL)
{
Prev = Ptr;
Ptr = Ptr->Next;
}
free(Ptr);
}
}
``````

Deletion after a particular node:
If we have the address of a particular node, we can always delete the node next to it.

Let us consider a linked list: 10→20→30→40.

Suppose we wish to delete 20 from it, we will delete the node containing 30 and then rewrite the value of 20 as 30.

The lines of code for doing this will be:

``````Ptr->data = Ptr->Next->data;
Ptr = Ptr->Next;
Ptr->Next = Ptr->Next->Next;
free(Ptr);
``````

Thus, after deleting 20, the new list will be 10→30→40.

To reverse a linked list, we need to reverse the pointers.

For example, if the list is 10→20→30→40,

On reversing we will have 10←20←30←40 and 10 will point to NULL.

The recursive approach to reverse a list is as follows:

``````int Reverse_list(struct Node *Head)
{
struct Node *remaining;

return remaining;
}
``````

1. The size of the linked list is limited to the memory size due to dynamic memory allocation. That is why, we need not declare the size of the list beforehand, rather we can do that at run time.

2. A linked list can never contain an empty node.

3. Although a linked list is a linear data structure, it is unnecessary to store it contiguously in the memory. This is because the list is connected through addresses/pointers. This helps in the efficient utilization of memory space.

## Linked List Implementations in Java

// Linked list implementation in Java

``````class LinkedList {
// Creating a node

static class Node {
int value;
Node next;

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

public static void main(String[] args) {

// Assign value values
Node second = new Node(2);
Node third = new Node(3);

// Connect nodess
second.next = third;

// printing node-value
}
}
}
``````
``````import java.io.*;

// Java program to implement

// This inner class is made static
// so that main() can access it
static class Node {

int data;
Node next;

// Constructor
Node(int d)
{
data = d;
next = null;
}
}

// Method to insert a new node
{
// Create a new node with given data
Node new_node = new Node(data);
new_node.next = null;

// If the Linked List is empty,
// then make the new node as head
}
else {
// Else traverse till the last node
// and insert the new_node there
while (last.next != null) {
last = last.next;
}

// Insert the new_node at last node
last.next = new_node;
}

// Return the list by head
return list;
}

// Method to print the LinkedList.
{

while (currNode != null) {
// Print the data at current node
System.out.print(currNode.data + " ");

// Go to next node
currNode = currNode.next;
}
}

// Driver code
public static void main(String[] args)
{

//
// ******INSERTION******
//

// Insert the values
list = insert(list, 1);
list = insert(list, 2);
list = insert(list, 3);
list = insert(list, 4);
list = insert(list, 5);
list = insert(list, 6);
list = insert(list, 7);
list = insert(list, 8);

printList(list);
}
}
}
``````

continue

# Linked list implementation in Python

``````class Node:
# Creating a node
def __init__(self, item):
self.item = item
self.next = None

def __init__(self):

if __name__ == '__main__':

# Assign item values
second = Node(2)
third = Node(3)

# Connect nodes
second.next = third

# Print the linked list item
``````

# Linked list implementation in php

First, you need to define a Node class that represents a single node in the linked list.

This class will have two properties: \$data which will store the data element of the node, and \$next which will store a reference to the next node in the sequence.

``````class Node {
// data stored in this node
public \$data;

// reference to the next node
public \$next;

// initialize the node with the given data
function __construct(\$data) {
\$this->data = \$data;
\$this->next = null;
}
}
``````

This class will have a \$head property that stores a reference to the first node in the list, and a \$tail property that stores a reference to the last node in the list.

``````class SinglyLinkedList {

// tail of the linked list
public \$tail;

function __construct() {
\$this->tail = null;
}
}
``````
``````<?php

class Node{
public \$data;
public \$next;
public \$visited;
public function __construct(\$data){
\$this->data = \$data;
\$this->next = null;
\$this->visited = false;
}
}

{
public \$count = 0;

public function insert(\$data)
{
//create a new node object with the data we want to insert. Takes O(n) time.
\$newNode = new Node(\$data);

//head node 'null' indicates there is no node in the list
//make the newnode as the head node
} else {
//else traverse throught last position and insert the new node at the last position

while (\$current->next != null) {
\$current = \$current->next;
}
//now 'current' next filed points to the new node we created
\$current->next = \$newNode;
}

\$this->display();
//increment the count indicating one node is entered in the list.
\$this->count++;
}
//takes O(1) time
public function insertAtFront(\$data)
{
\$newNode = new Node(\$data);

} else {
//store the current head node in a variable.

//make the new node we want to insert as the head node.
//make the new node next field point to the previous head node that is in 'currentHead' variable
}

\$this->display();
\$this->count++;
}

//takes O(n) time
public function insertAtPosition(\$data, \$position)
{
\$newNode = new Node(\$data);

//if the position is zero call the insertAtFront method, position zero indicates that we want ot insert the node at the front of the list
if (\$position == 0) {
\$this->insertAtFront(\$data);
} else {
//traverse the node until we reach the position
for (\$i = 1; \$i < \$position; \$i++) {
\$current = \$current->next;
}
//now the current node contains the node we want to insert at the given position.
//make the new node's next field to point to the 'current' node's next node.
\$newNode->next = \$current->next;
//make the 'current' node next field to point to the new node
\$current->next = \$newNode;

}
\$this->display();
\$this->count++;
}

//takes O(n) time
public function display(){
//traverse the list
while(\$current != null){
//while traversing print the data field of the current node we are traversing
echo \$current->data ,"->";
\$current = \$current->next;
}
//not compulsory..to just indicate that we reach the end of the list
echo "NULL";

echo "\n";
}

//takes O(1) time
public function deleteFirst(){
//if the head node is null there is no element to be deleted...a simple check whether the head node is not null

//checking if the head node's next field is not null..if it is null there is only head node is present in the list...'else' block covers this case
}
}else{
}
\$this->display();
//decrement the count indicating a node is deleted from the list
\$this->count--;
}

//takes O(n) time
public function deleteLast(){
}else{
//traverse until u reach the last position of the list
while(\$current->next != null){
//keep track of the previous node while traversing
\$prev = \$current;

\$current = \$current->next;
}
//set the previous node's next to point null...thus the last node lose its reference
\$prev->next = null;

}
}

\$this->display();
\$this->count--;
}

public function delete(\$data){

//if the data is the 'headnode' call delete first method
\$this->deleteFirst();
}
\$prev = null;
//traverse the list
while(\$current->next != null){
//if the data matches the current node's data we are iterating..
if(\$current->data === \$data){
//if we are at last..
if(\$current->next == null){
\$prev->next  = null;
}else{
// else point the previous node's next pointer to point to the current node we are iterating next node.
\$prev->next = \$current->next;
}
}
//keep track of the previous node while we are iterating
\$prev = \$current;
\$current = \$current->next;
}
}

\$this->display();
\$this->count--;
}
}
``````

Insertion After target Node:

Insertion at begining:

deletion at first:

deletion at last:

deletion at given position: