Home Data Structure and Algorithm Linked list Data Structure

# Linked list Data Structure

In this tutorial, you will learn about linked list data structure and it’s implementation in Python, Java, C, and C++.

Linked List is a linear data structure. Unlike arrays, linked list elements are not stored at a contiguous location; the elements are linked using pointers.

## Why use linked list over array?

Arrays can be used to store linear data of similar types, but arrays have the following limitations.

• The size of the arrays is fixed, So we must know the upper limit on the number of elements in advance.
• Inserting a new element in an array of elements is expensive because the room has to be created for the new elements and to create room existing elements have to be shifted.

## What is Linked List ?

Linked List can be defined as collection of objects called nodes that are randomly stored in the memory.

A node contains two fields i.e. data stored at that particular address and the pointer which contains the address of the next node in the memory.

The last node of the list contains pointer to the null.

Linked lists can be of multiple types: singlydoubly, and circular linked list

## Linked List Complexity

Time Complexity

Worst caseAverage Case
SearchO(n)O(n)
InsertO(1)O(1)
DeletionO(1)O(1)

## Applications of linked list data structure

• Implementation of stacks and queues.
• Implementation of graphs
• Dynamic memory allocation
• Maintaining directory of names.
• In undo functionality of softwares