Linked List Introduction

Introduction

• In memory a linked list is a data structure that consists of a sequence of data records in a such way that each record there is a field that contains a pointer to the next record in the sequence.

• Each record of a linked list is often called an element or node.

• Each element of the list contains the address of the next node is usually called the next link or next pointer and remaining fields are known as data, or information, or value, or cargo,or payload fields.

• The first node/element of the list is called 'Head' or Car and last node is called 'Tail' or CDR (pronounced could-er).

• Linked list are classified into three types of linked list

1. Single linked list
2. Double Linked list
3. Circular linked list
1. Single Circular linked list
2. Double Circular linked list

Advantages of Linked List

• Linked List is Dynamic data structure so they can grow and shrink during run time

• On Linked list Insertion and Deletion Operations are Easier

• Efficient Memory Utilization i.e no need to do any pre-allocation like Array.

• Faster Access time,can be expanded in constant time without memory overhead in circular linked list.

• Linear Data Structures such as Stack,Queue can be easily implemented using Linked list.  

Disadvantages of Linked List

• Extra memory is needed for storing the next link information using pointer. 

• Array can be randomly accessed , while the Linked list cannot be accessed Randomly.

• Individual nodes/elements are not stored in the contiguous (continues) memory Locations.