Simple Data Structure

The term Data Structure means data collection with well defined operations and behavior or properties.

The term Linked list refers to a linear data structures with non contiguous memory.

Or

The linked list is a collection of linear data elements called node stored in a non contiguous memory(Stored randomly anywhere in the memory).

Note: If the data is stored randomly anywhere in the memory how to access it, we have Linked List to overcome this problem, it is linked with the help of address where each block carries address of successive block or previous block or node.

A node contains two parts :

i: data

ii: address

Advantage over arrays:

i : Arrays does not have dynamic memory

ii : Easily insertion/Deletion

Linked List

There are four basic Linked list

1. SLL(Singly Linked List)
2. CLL(Circular Linked List)
3. DLL(Doubly Linked List)
4. CDLL(Circular Doubly Linked List)

Linked List Image (Source : AlphaCodingSkills)

1.Singly Linked List

In Singly Linked List the very first node is called or pointed as Head and if you want to know the last node it points to null.

Note : The node part contains the address of the successor node so we can not traverse in reverse direction to overcome this problem we have Doubly Linked List lets see how.

class LinkedList
{
 Node head;
 class Node
 {
  int data;
  Node next;
  Node(int d)
 {
data = d; next = null; 
  }
 }
}

2.Doubly Linked List

It also contains nodes. There is one data and two address pointers in a single node in which one address which points to its previous node, and one points to the next node.

Doubly Linked List

You can see in the picture that each node contains one data and two address one points to the address of next node and one points to the address of previous node. The first and last node points to the null. In the very first node the prev address shows null as it does not have any previous value and in the very last node the next pointer shows null value.