CS Code

Programmer Community

In this tutorial, we are going to learn the Linked List Data Structure, Structure of Node, Applications of Linked List and Linked List Over Array.

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

• A node is divided into at least two parts:
• Data Part
• Next Part

Data part: Data part is used to store actual data. For example, name of the student, roll number, class and any data related to that student.

Next part: Next part is nothing but a pointer which stores address of the next node.

Starting node is also called as `Head` . The next part of the end node is set to `NULL`.

## Why Linked List over Array?

Of-course we choose Linked List to perform insertion, deletion, updation and searching on 1 Million records.

Why?

• Insertion of new element in the array is too expensive. If we have to insert an element at position 1 then we have to shift all the elements from position 1 to the end by 1.
• int arr[100000] = {1, 2, 3, 4, ……., 99999};
• suppose we have to insert a new number(0) at index 0 then we have to shift all the numbers by index 1 to right.
• {0, 1, 2, 3, 4, …..} (0 takes position of 1, 1 takes position of 2 and so on).
• Same problem while deleting the elements from array.

• Dynamic size.
• Non-contiguous memory allocation
• Ease of insertion/deletion

• Can not access elements randomly in the Linked List. In array elements can be accessed randomly using array index(ex. arr[4]). This is not possible in linked list.
• Required extra space to store next pointer for all nodes.
• Linked List is not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not there in case of linked lists.

In C, node can be represented using Structure.

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

class Node {
int data;
Node next;

// Constructor to create a new node
// Next is by default initialized
// as null
Node(int d) { data = d; }
}
}```
```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):