Introduction
In this article, I am going to discuss one of the most important Data Structures- Linked List.
I will be explaining about
- Linked List
- Advantage of Linked List
- Types of Linked List
- How to Create a Linked List
- Various operations on Linked list.
What is a Linked List?
Linked List is a linear data structure which consists of a group of nodes in a sequence. Each node contains two parts.
- Data Each node of a linked list can store a data.
- Address Each node of a linked list contains an address to the next node, called "Next".
The first node of a Linked List is referenced by a pointer called Head
Advantages of Linked List
- They are dynamic in nature and allocate memory as and when required.
- Insertion and deletion is easy to implement.
- Other data structures such as Stack and Queue can also be implemented easily using Linked List.
- It has faster access time and can be expanded in constant time without memory overhead.
- Since there is no need to define an initial size for a linked list, hence memory utilization is effective.
- Backtracking is possible in doubly linked lists.
Types of Linked List
- Singly Linked List: Singly linked lists contain nodes which have a data part and an address part, i.e., Next, which points to the next node in the sequenceof nodes. The next pointer of the last node will point to null.
- Doubly Linked List: In a doubly linked list, each node contains two links - thefirst link points to the previous node and the next link points to the next node in the sequence.Theprev pointer of the first node and next pointer of the last node will point to null.
- Circular Linked List: In the circular linked list, the next of the last node will point tothe first node, thus forming a circular chain.
- Doubly Circular Linked List: In this type of linked list, the next of the last node will point to the first node and the previous pointer of the first node will point to the last node.
Creating a Linked List
The node of a singly linked list contains a data part and a link part. The link will contain the address of next node and is initialized to null.So, we will create class definition of node for singly linked list as follows -
- internalclassNode{
- internalintdata;
- internalNodenext;
- publicNode[intd]{
- data=d;
- next=null;
- }
- }
The node for a Doubly Linked list will contain one data part and two link parts - previous link and next link.Hence, we create a class definition of a node for the doubly linked list as shown below.
- internalclassDNode{
- internalintdata;
- internalDNodeprev;
- internalDNodenext;
- publicDNode[intd]{
- data=d;
- prev=null;
- next=null;
- }
- }
Now, our node has been created, so, we will create a linked list class now.When a new Linked List is instantiated, it just has the head, which is Null.The SinglyLinkedList class will contain nodes of type Node class. Hence, SinglyLinkedList class definition will look like below.
- internalclassSingleLinkedList{
- internalNodehead;
- }
The DoublyLinkedList class will contain nodes of type DNode class. Hence, DoublyLinkedList class will look like this.
- internalclassDoubleLinkedList{
- internalDNodehead;
- }
Various operations on Linked list
Insert data at front of the Linked List
- The first node, head, will be null when the linked list is instantiated. When we want to add any node at the front, we want the head to point to it.
- We will create a new node. The next of the new node will point to the head of the Linked list.
- The previous Head node is now the second node of Linked List because the new node is added at the front. So, we will assign head to the new node.
- internalvoidInsertFront[SingleLinkedListsinglyList,intnew_data]{
- Nodenew_node=newNode[new_data];
- new_node.next=singlyList.head;
- singlyList.head=new_node;
- }
- internalvoidInsertFront[DoubleLinkedListdoubleLinkedList,intdata]{
- DNodenewNode=newDNode[data];
- newNode.next=doubleLinkedList.head;
- newNode.prev=null;
- if[doubleLinkedList.head!=null]{
- doubleLinkedList.head.prev=newNode;
- }
- doubleLinkedList.head=newNode;
- }
Insert data at the end of Linked List