LinkList

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

Why Linked List? Arrays can be used to store linear data of similar types, but arrays have following limitations.

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

Representation

A linked list is represented by a pointer to the first node of the linked list. The first node is called head. If the linked list is empty, then value of head is NULL. Each node in a list consists of at least two parts:

1. data
2. Pointer (Or Reference) to the next node In C, we can represent a node using structures. Below is an example of a linked list node with an integer data. In Java, LinkedList can be represented as a class and a Node as a separate class. The LinkedList class contains a reference of Node class type.