Linked List Operations: Traverse, Insert and Delete

 

Linked List Basics

A linked-list is a sequence of data structures which are connected together via links.

Linked List is a sequence of links which contains items. Each link contains a connection to another link. Linked list the second most used data structure after array. Following are important terms to understand the concepts of Linked List.

• Link − Each Link of a linked list can store a data called an element.

• Next − Each Link of a linked list contain a link to next link called Next.

• LinkedList − A LinkedList contains the connection link to the first Link called First.

Linked List Representation

As per above shown illustration, following are the important points to be considered.

• LinkedList contains an link element called first.
• Each Link carries a data field(s) and a Link Field called next.
• Each Link is linked with its next link using its next link.
• Last Link carries a Link as null to mark the end of the list.

Types of Linked List

Following are the various flavours of linked list.

• Simple Linked List − Item Navigation is forward only.

• Doubly Linked List − Items can be navigated forward and backward way.

• Circular Linked List − Last item contains link of the first element as next and and first element has link to last element as prev.

Basic Operations

Following are the basic operations supported by a list.

• Insertion − add an element at the beginning of the list.

• Deletion − delete an element at the beginning of the list.

• Display − displaying complete list.

• Search − search an element using given key.

• Delete − delete an element using given key.

Types of Linked List

1. Singly Linked List

It is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type. 

The node contains a pointer to the next node means that the node stores the address of the next node in the sequence. A single linked list allows the traversal of data only in one way

2. Doubly Linked List

A doubly linked list or a two-way linked list is a more complex type of linked list that contains a pointer to the next as well as the previous node in sequence. 

Therefore, it contains three parts of data, a pointer to the next node, and a pointer to the previous node. This would enable us to traverse the list in the backward direction as well

3. Circular Linked List

A circular linked list is that in which the last node contains the pointer to the first node of the list. 

While traversing a circular linked list, we can begin at any node and traverse the list in any direction forward and backward until we reach the same node we started. Thus, a circular linked list has no beginning and no end. Below is the image for the same: