# Linked List Data Structure (Introduction) ## What are Linked List in Data Structure?

A linked list is a linear data structure. In which we can sequentially store the data. Unlike an array linked list is a dynamic data structure the size of a linked list can grow or shrink depending on the situation.

However, in the case of Arrays, we need to predefine the size and we can’t add more items than the max size defined.

The element of a linked list is called a node. Every element or node contains two main entities first entity is the information or the data whereas the second entity is the pointer to the next node.

The structure of the linked list is like a train. A linked list has the following components –

• Data: Data is the value stored in it, it could be anything an integer or a string or anything else really.
• Pointer (Link) – Each linked list contains a pointer which points to address of the next node in the linked list train.

Apart from this the following are also keywords used in linked lists –

• Node – Any single unit of a linked list, its data and pointer(s), is called a node.
• Head: First is the head who is defined the beginning of the list.
• Tail: second is tail which defined end of the list. ## Why we use Linked List in Data Structure?

Generally for storage arrays are used. But, there are many many disadvantaged with arrays –

### 1. Fixed Size

• The size of the array is fixed and needs to be pre-defined
• Example – `int a;` or `int a[ ] = {1, 2, 3, 4, 5}`
• We can’t declare an array without declaring the size.

### 2. Memory wastage (Not Optimised)

• If you declare an array of size 10 and just assign values to first two elements
• The memory is allocated to all of them even though, we may not end up using them.

### 3. Need for Contiguous Memory

• Arrays need Contiguous memory, which some times is bad.
• Example – Consider there are only three memories of size 10, 10 and 400
• We need to store an array of size 15
• In this case, the array will use memory location is size 400 and not combine memory A and B of size 10 and 10 respectively.
• Thus wasting a lot of memory

### 4. Inserting in Array is expensive

• Let us say you have an array a[] = {10, 20, 40, 60, 80} and we need to add 50 in a same sorted format.
• Then, we have to move all elements after 40 to one additional position
• Also, same goes for deletion if we want to delete 20. Then all elements after it have to be moved to one position in the opposite direction.

• We have to search elements linearly, and can’t do random access
• We can’t do efficient searches like binary search
• Extra space for pointers is needed
• Linked lists are not cache friendly as arrays are stored in contigious format they can be cached easily
• Loss of data threat is there, if we lose one pointer location the rest of linked list can’t be accessed.

There are three types of linked list, that are mentioned in following ways-

In a singly list there is the two field on the list.

• Data: First field is data that it stores
• The last node of linked lits points to NULL and means the end of the list

In a Singly linked list node, it only contains the address of the next node and not the previous node, so we can only traverse in one direction only. ## Structure of Singly Linked List

```struct Node {
int data;
struct Node* next;
};```
```class Node {
public:
int data;
Node* next;
};```
```class LinkedList {
class Node {
int data;
Node next;

// constructor to initialize
Node(int d) {
data = d;
}
}
}```
```# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize
# next as null

# Function to initialize the Linked
# List object
def __init__(self):

## Program to Create a Singly List

Here we will construct a linked list with 4 elements as follows – Run
```//We are creating program for linked list creation
#include<stdio.h>
#include<stdlib.h>
//stdlib used to provide a declaration of ‘malloc’

struct Node {
int data;
struct Node* next;
// Pointer pointing towards next node
};

//function to print the linked list
void display(struct Node* node)
{
while (node != NULL) {
printf(" %d ", node->data);
node = node->next;
}
}

// main function
int main()
{
//creating 4 pointers of type struct Node
//So these can point to address of struct type variable
struct Node* node2 = NULL;
struct Node* node3 = NULL;
struct Node* node4 = NULL;

// allocate nodes in the heap via memory allocation using malloc
node2 = (struct Node*)malloc(sizeof(struct Node));
node3 = (struct Node*)malloc(sizeof(struct Node));
node4 = (struct Node*)malloc(sizeof(struct Node));

/* Using malloc method we have created 4 memory blocks
Each memory block is of type struct and has int data and Pointer of type Node
So it can point towards a node type struct.

|                |               |               |
|                |               |               |
+---+-----+     +----+----+     +----+----+     +----+----+
|data|next|     |data|next|     |data|next|     |data|next|
+---+-----+     +----+----+     +----+----+     +----+----+

# As of now data has garbage value and its pointer

node2->data = 100;
node2->next = node3;

node3->data = 150;
node3->next = node4;

node4->data = 200;
node4->next = NULL;
//last node assigned to Null as linked list ends here

/* Finally linked list looks like

|                |               |               |
|                |               |               |
+----+-----+     +-----+-----+     +-----+-----+     +-----+------+
| 50 | next|---->| 100 | next|--->| 150 | next |---->| 200 | next | ---> NULL
+----+-----+     +-----+-----+     +-----+-----+     +-----+------+

*/

return 0;
}```
Run
```#include<iostream>
using namespace std;

class Node
{
public:
int data;
Node *next;
};

void display(Node* node){

// as linked list will end when Node is Null
while(node!=NULL){
cout << node->data << " "; node = node->next;
}
cout << endl;
}

int main(){

//creating 4 pointers of type Node
Node* node2 = NULL;
Node* node3 = NULL;
Node* node4 = NULL;

// allocate memory in the heap
node2 = new Node();
node3 = new Node();
node4 = new Node();

/* Using new method we have created 4 memory blocks Each memory
block is of type Node and has int data and Pointer of type Node
So it can point towards a node class object/pointer.
|                     |                   |                  |
|                     |                   |                  |
+-----+------+     +------+------+     +------+-----+     +------+------+
| data | next|     | data | next |     | data | next|     | data | next |
+-----+------+     +------+------+     +------+-----+     +------+------+

//  As of now data has garbage value and its pointer points towards random addresses*/

// since we are working with pointers we use ->
// instead of . with object pointers

head->next = node2; // next pointer assigned to node2

node2->data = 100;
node2->next = node3;

node3->data = 150;
node3->next = node4;

node4->data = 200;
node4->next = NULL; //last node assigned to Null as linked list ends here

/* Finally linked list looks like

|                  |                |                 |
|                  |                |                 |
+----+-----+     +-----+----+     +-----+----+      +-----+----+
| 50 | next|---->| 100 | next|--->| 150 | next|---->| 200 | next| ---> NULL
+----+-----+     +-----+----+     +-----+----+      +-----+----+

*/

return 0;
}```

A doubly linked list is a kind of complex linked list, in which it contains the address of the previous node as well as the next node. A doubly linked list contains the following –

• Data: The data present in the node.
• Link (Previous) – A pointer to the previous node in the linked list.
• Link (Next) – A pointer to the next node in the linked list

In this way, for a doubly-linked list we can travel in both directions for traversals. ## Structure of Doubly Linked List

```struct Node {
int data;
struct Node* next, prev;
};```
```class Node {
public:
int data;
Node* next, prev;
};```
```class LinkedList {
class Node {
int data;
Node next, prev;

// constructor to initialize
Node(int d) {
data = d;
}
}
}```
```# Node class
class Node:
# Function to initialize the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize    # next as null   self.prev = None # Initialize    # prev as null

# Function to initialize the Linked
# List object
def __init__(self):

• This is a type of linked list in which the last node points to the starting node.
• There is no null at the end.
• A circular linked list can be a singly circular linked list and doubly circular linked list.
•  In Circular linked list there exist no nodes which have null at address space.  • Divya

I want the materials to learn Data structures with Python. 1
• Itzz Akanksha

How to implement linkedlist in java , as in java there is no concept of pointers. 1
• HelpPrepInsta

Pointers are there in Java also.
I hope this will resolve your query 0
• Jaspreet

How to solve linked list problems in python? 1
• Care

You cannot implement Linked List in Python, as Python doesn’t have the concept of Pointers. But in Python you can use List, or other data structures like Dictionaries which may help you in storing the data efficiently 5
• chellabangarkrishna

You can implement in Python as Well !
here is the sample Code!

class Node:
def __init__(self, value):
self.value = value
self.next = None
def __init__(self):
def insert(self, value, location):
newNode = Node(value)
else:
#Begining loc = 0
if location == 0: 0