Linked List in java

In this article we will discuss about linked list 
in data structure using java programming 
language.I had already posted Introduction
to Data Structure . while you develop computer
programming software projects you should 
include linked list data structure to organize 
your data in the computer memory.







Linked list is a common and simple data structure.This data structure comes under linear data structure which consists of group of nodes and  the elements are stored in the sequence order in the computer memory. A node contains two fields,they are Data item & Link address.Data Item contains actual value and link contains next node address. In this we use a special pointer called HEAD, contains first node address.

Difference between Array and Linked List:

Array:

• Array is a collection of Homogeneous elements
• we can easily identify a particular element in the list
• It is a static Data structure
• Here is size is fixed

Linked List:

• Linked list is a linear data structure
• It is not easy to identify a particular element in the list
• It is a dynamic Data Structure
• Here size is not fixed

Advantages of Linked List:

1. we can easily implement stack,queue using linked list
2. we can easily insert and delete elements in the list
3. linked list has dynamic nature so memory size increase automatically. So we need to know the size in advance

Types of Linked Lists:

Lined Lists are three types. They are

1. Singly Linked List

2.Doubly Linked List

3.Circular Linked List

Singly Linked List:

It is a collections of linear data elements.In this an element is referred as a node. A node contains two fields,they are data item & link address. Data item contains actual value and link contains next node address.Int this we use a special pointer called HEAD,contains first node address.It means singly linked list first node address will be store in the Head pointer.Last node link contains the NULL pointer.

The representation of single Linked List is as follows:

we can develop the single linked list by using the following operations:

1.Creation

2.Traversing

3.Insertion

4.Deletion

1.Creation:

To create a linked list first we check the condition whether the head is null or not. If the head is null then create a new node and assign that address to the head. Otherwise create a new node and assign that address to the previous node link.

Algorithm:

Step 1: Start

Step 2: if(Head==NULL)

                p=new node

                p---->data=num

                p---->link=NULL

                head=p

Step 3: else

                t=new node

                t----->data=num

                t----->link=NULL

                p---->link=t

                p=t

Step 4: stop

2.Traversing:

In this we display each and every element in the list.In single linked list traversing can possible only one direction that is from head to last element.

Algorithm:

Step 1: Start

Step 2: Set a=head

Step 3: Repeat the steps 4,5 while(a!=NULL)

Step 4: print a----->data

Step 5: set a=a----->link

Step 6: stop

3. Insertion:

In single linked list we can insert the element in three ways: they are

1. Insert the element at the beginning of the list

2.Insert the element at the end of the list

3.Insert the element at after specified node

Insert the element at the beginning of the list:

If we want insert the element at the beginning of the list then we create new node and assign that new node address to the head and also establish to the next node.

Before Insertion:

After Insertion:

Algorithm: insert-beginning(num)

Step 1:  Start

Step 2: t=new node

step 3: t----->data=num

Step 4: t------>link=head

step 5: head=t

step 6: Stop

Insert the element at the end of the list:

To insert the element at the end of the list we can create a new node and assign that node address to previous node link and assign NULL Pointer.

Before Insertion:

After Insertion:

Algorithm:  Insert-ending(num)

Step 1: Start

Step 2: t=new node

step 3: t----->data=num

step 4: t----->link=NULL

step 5: p----->link=t

step 6: p=t

step 7: Stop

Insert the element at the after specified node:

To insert an element at the specified node first we check the whether the node is in the list or not. If the specified node is found then that node points to the new node element and the node element points to the next node.Otherwise display element is not found.

Before Insertion:

After Insertion:

Algorithm: Insert-after(ele,num)

Step 1: Start

Step 2: set a=head

Step 3: repeat the steps 4&5 while(a!=NULL)

Step 4: if(ele==a--->data)then

               t=new node

               t----->data=num

               t----->link=a----->link

               a----->link=t

Step 5: else

               a=a----->=t

Step 6: Stop

Deletion:

If we want to delete an element from the list we can follow two methods:

a. if the deleted element is first element,then assign second node address to the head.

b. if the deleted element is middle element,then assign next node address to the previous node.

Before Deletion:

After Deletion:

Algorithm: deletion(num)

Step 1: Start

Step 2: set a=head

Step 3: if(a---->data==num)then

              head=a----->link,delete a;

step 4: else

               set b=a,

               set a=a----->link

step 5: repeat the steps 6&7 while(a!=NULL)

Step 6: if(a---->data==num)then

                b---->link=a---->link

              delete a;

step 7:  else

                 set b=a

                 a=a----->link

Step 8: Stop

Read also this post: TOP HR interview Questions for freshers