Linked List
Linked List

Linked List

Hello readers! How are you all? Today also I am bringing a post related to the data structures and algorithms. So far we have discussed about stacks and queues. So today we are going to see information about singly linked list implementation. This is also a very interesting topic to discuss. Let’s get started.

Post outline

  • What are linked lists
  • Components of pointers
  • Constructors use to create nodes
  • Linked list operations
  • How singly linked list operations work
    • Initialization
    • Add to head
    • Add to tail
    • Delete from head
    • Delete from tail
    • Temp node in linked list deletion
  • Linked list implementation code
    • Code for implementing the list 
    • Code for implementing linked list node
  • Quick Rap

What are linked lists?

Linked lists are also a data structure we commonly use in programming. We have two types of linked lists. One is singly linked list other one is doubly linked lists. These are created by using nodes. Here today we will discuss how to create a node. How to implement a linked list. How singly and doubly linked list works. As other data structures linked list also has two ends. They are the tail and head. We can add and remove nodes from head and tail. Linked list can implement using an array or pointers. Today we will discuss linked list using pointers.

Components of pointers

The pointers has two components. They used to create a linked list. Pointers also known as nodes. A node components are info and next. Info means the data part. It contains the data items which we inserted to the list. Next refers the link part. That means linked list are connected to one another. The nodes have a address. They identified nodes by using this. So next refers the connecting node address. As an example if a node address is 99 and it’s next value is 100. Then 99 node will linked to the 100 node.

Constructors use to create nodes

We use constructors to create objects. Before we implement the code for a linked list firstly we have to implement the nodes. Like stacks or queues we can’t directly implement this code. These are created using pointers/nodes. Therefore we firstly learn how to create a pointer. You already know there are two parts in a pointer. Therefore we can create a node with three types. Those are,

  • Pointer have null info and null next
  • Pointer have a value for info and null next
  • Pointer have a value for info and value for next

For these three types we create constructors.

Constructors in Linked list
Constructors in Linked list

Linked list operations

Like stacks and queues linked list also can perform set of operations. We create methods for them. Those operations are,

  • Initialization
  • Add to the head
  • Add to the tail
  • Delete from head
  • Delete from tail
  • Insert to middle
  • Delete from middle

We are now going to learn how these operations. Because to understand the code firstly we need to understand how it will work for these above operations.

How singly linked list Operations work

Initialization

A list has two special nodes. Those we known as head and tail. You already know that there are two parts in a node. They are info and next. In head and tail there is no any info. We use head and tail to identify the first connecting node and last node. Head implies the starting node in the list. Tail implies the last node in the list.  When we initialize or created a list the both head and tail value will be null.

Head and tail node in initialization
Head and tail node in initialization

Add to the head

When adding a node to the head the head will connected with the new node. Head will take the new node value. If there is a one node tail also take the new node value. If we are adding a node to the head when there is node. Then only head value will change

"<yoastmark
This image shows add to head operation

 

"<yoastmark
Add to head operation explanation

Add to the tail

This add to the tail is also similar like add to the head. When there is no nodes both the head and tail will take node address. When there is a node and adding anew node, tail will take the new node value. It will replace the old value with new. Head value will remain same. Old node next value will replace with new node address value.

Add node A to tail
Add node A to tail

 

Add to tail for not empty linked list
Add to tail for not empty linked list

Delete from head

When it comes to deleting from the head also has two options. One is when deleting there is only one node. Other one is when deleting there is multiple nodes. Deleting from head will delete the node which head connected. The node which owns the value in the head will delete. We firstly discussed the first one. When delete from head there is only one node both head and tail consist the same value. That the node address. It will replace with null after deletion. When there is node already exist in the list scenario is little bit different. Tail value will remain as same. Head value will replace with the value which is next to the current head.

As an example there is a list with three nodes and their addresses are 99,100,101

Head value = 99

Tail value = 101

After deletion head value = 100

After deletion tail value = 101

Deletion node value = 99

Delete from head
Delete from head

Delete from tail

Deleting from tail is also similar like delete from head. When deleting from the tail the node value which tail consist will be deleted. As we discussed in the head here also we have two states. That is deleting from tail when there is one node and there is many nodes. When there is only one node both head and tail values will be null and the node will remove from the list. When there is many nodes the tail value will replace with the node value which is the previous node to the current node.

As an example there is four nodes in a list and node values are, 99,100,101,102.

Head value -99

Tail value -102

Tail value after deletion – 101

Head value after deletion – 99

Deleted note – 102

Node which is previous to the current node – 101

Delete from tail
Delete from tail

 

Delete from head/tail when only one node in list
Delete from head/tail when only one node in list

Temp node in linked list deletion

When deleting use an extra node called temp. We use it deleting from deleting a node from tail. When deleting from head we don’t need this. That is because list is aware about the head. The list start from the head. When head delete it knows next node to connect and maintain the list. When it comes to tail it doesn’t know what is the node before to the current tail. Because of that it has to travel until it find the tail.  Therefore use node called temp and assign head value to it. Then it check whether temp.next value == tail value. If not it will take the temp.next vale. Temp.next value means it takes the next value in the temp node.

As an example we will take the previous list.

Head vale = 99

Tail value =102

99 node next value = 100

100 node next value = 101

101 node next value = 102

First temp value = 99 (which is the head value)

Second temp value =  (Which is temp.next = 99.next = 100)

When temp is 101. Temp.next is 102. At that time temp.next  = tail value. So now tail can take the temp.next value and delete tail node from the list. That’s why we use temp node for deletion. To identify the node before tail.

Linked list implementation code

Code for Implementing linked list 

</span></p>
<pre class="wp-block-syntaxhighlighter-code"><span style="font-family: arial, helvetica, sans-serif;">
public class List{
	Protected Node head,tail;
	
	public void list(){
		head=tail=null;
	}
	
	public boolean isEmpty(){
		return head ==null;
	}
	
	public void addToHead(){
		head = new Node(el,head);
		if(tail=null)
			tail=head;
	}
	
	public void addToTail(char el){
		if(tail==null)
		head=tail=new Node(el);
	else{
		tail.next = new Node(el);
		}
	}
	
	public char deleteFromHead(){
		char el = head.info;
		if(head==tail){
		head=tail=null;}
		else{
			head=head.next;
		return el;}
	}
	
	public char deleteFromTail(){
		char el = tail.info;
		if(head==tail){
			head=tail=null;
		}
		else{
			Node temp;
			for(temp=head;temp.next!=tail;temp=temp.next);
				tail=temp;
				tail.next = null
			return el;
		}
		
	}
	
	public void delete(char el){
		if(head==tail && el==head.info){
			head=tail=null;
		}
		else{
			head=head.next
		}
		else{
			Node temp,pred;
			for(pred=head,temp=head.next; temp!=null && temp.info !=el; pred=pred.next,temp=temp.next);
				if(temp!=null){
					pred.next=temp.next;
					if(temp==tail){
						tail=pred;
					}
				}
			
		}
	}
}</span></pre>
<p><span style="font-family: arial, helvetica, sans-serif;">

Code for Implementing Linked list Node

</span></p>
<pre class="wp-block-syntaxhighlighter-code"><span style="font-family: arial, helvetica, sans-serif;">Public class Node{
Public char info;
public Node next;

public Node(){
next=null;
} 
public Node(){
info =el;
next=null;
}
public node(char el, Node ptr){
info=el;
next=ptr;
}
}</span><br /><br /></pre>
<p><span style="font-family: arial, helvetica, sans-serif;">

Quick Rap

  • Singly linked list are made from pointers.
  • Those pointers have two parts. They are info and next.
  • Info – what is the element inside node
  • Next – next node address
  • The operations can perform in a list
    • Add to head
    • Add to tail
    • Delete from head
    • Delete from tail
    • Insert a node
    • Delete a node

Conclusion

With this I am concluding this post. Today we discuss about singly list. I will write another post for doubly linked list. Doubly linked list working and their implementation code is little bit different than singly linked list. There is another explain about middle insert and deletion. I will write a post regarding that also. To explain the code of the linked list another post also I will use. We will meet with those topic soon. Till then goodbye all!

Audy Ranathunga

Audy Ranathunga, Author of myexamnote is our most experienced author. She has been working as a blog post writer for 4 years. She joined with myexamnote before 1 year ago and she has contribute lots of valuable posts for readers.

Leave a Reply