Background:
We have already discussed Array data structure. Memory allocation for an array is sequential in the nature. Means memory allocation for all array cells will be in sequence.
Memory - System memory is divided into chunks called frames. Due to continuous allocation and deallocation of the memory frames from CPU for different processes, available memory frames are scattered as given below in the diagram.
Here we can see maximum number of sequential frames available for memory allocation is 3. So any array having size more than 3 frames equivalent of the above mentioned memory couldn't be allocated here.
Based on the above observation we can say there are two major problems with array which are following:
1. The maximum size of an array which will be allocated to a system is subject to the availability of maximum free contiguous frames in the system memory.
2. Array is static data structure. Once an array is created with given size, it's size can't be modified based on application demand.
Linked list - Introduction
We discussed problems associated with the array in the above section. Linked list overcomes the above highlighted problems faced by an array. The major advantage of using linked list over the array is following:
1. There is no dependency on contiguous frames availability in the memory while allocating memory for linked list. All scattered frames can be used by linked list to allocate memory.
2. Linked list is dynamic in nature. At any time based on the application demand, the size of the linked list can be increased or decreased. Below figure shows physical presence of linked list in the system memory.
Definition -
Linked list is user defined, dynamic and linear data structure. It is set of linked list nodes connected to each other through address part(next pointer) of the linked list node. Below figure shows a linked list node.
Components of the linked list:
1. Head Pointer - It contains the address of the first linked list node.
2. Address/Next pointer - Each linked list node has an address part which points to next linked list node. If not next node present then its value is null.
3. Data part- Each linked list node has data part which contains data as unit of storage medium.
Strategy
Since linked list is set of linked list Nodes so here two classes are required to implement linked list which are as below.
1. LinkedListNode - This class will only define structure of linked list node.
2. LinkedList - This class will implement all necessary logic to operate linked list using linked listNode as storage unit. Below are the basic operations in the linked list.
a. head pointer - This is the pointer which always points to the first node of the linked list.
b. add()-This operation adds a element to the linked list at last position.
c. delete()-This operation deletes an element in the linked at last position.
d. printLinkedList()-This operation will print all element of the linked list.
Note: Here only basic operations of linked list has been implemented. There might be many more operation which can be applied on the linked list. We will see some of them in upcoming tutorials.
Below is the class diagram for the implementation of the linked list mentioned above:
Here we are going to write algorithms for all the operations of the linked list mentioned in the above diagram.
add( item )- Since this algorithm adds the element at the end of the linked list, Every time a new element is added we have to traverse to last node of the linked list using head pointer. So time complexity of add operation here will be O(n). Below is the algorithm for the same.
add(item)
{
1. tempHead=head
2. newNode=new LinkedListNode(item)
3. while(tempHead!=null && tempHead.next!=null)
4. tempHead=temHead.next
5. if(tempHead=null)
6. head=newNode
7. else
8. tempHead.next=newNode
}
delete( )- This operation deletes the last inserted element from the linked list. To delete the last inserted element, we have to traverse the linked list till the last node using head pointer. So time complexity to delete the last element here is O(n). Below is the the implementation of delete() operation.
delete()
{
1. if head == null
2. Error("No item present to delete");
3. tempHead=head
4. while(tempHead!=null && tempHead.next!=null && tempHead.next.next!=null)
5. tempHead=temHead.next
6. if(temHead.next==null)
7. head=null
8. else
9. temHead.next=null
}
printLinkedList()- This operation prints all the elements of the linked list by traversing the linked list using head pointer. Since entire linked list is traversed here, time complexity of this operation is O(n)
printLinkedList()
{
1. if head == null
2. Error("No item present in the linked List");
3. tempHead=head
4. while(tempHead!=null)
5. print(tempHead.data)
6. tempHead=temHead.next
}
Below is the java code implementation of the above discussed algorithms
public class LinkedListTest {
/**
* @param args
* @throws Exception
*/
public static void main(String[] args) throws Exception {
// TODO Auto-generated method stub
LinkedList<Integer> linkedList=new LinkedList<Integer>();
linkedList.add(1);
linkedList.add(2);
linkedList.add(5);
linkedList.add(6);
linkedList.add(11);
linkedList.printLinkedList();
linkedList.delete();
linkedList.delete();
System.out.println("LinkedList after deleting two elements");
linkedList.printLinkedList();
}
}
class LinkedListNode<T>
{
public T data;
public LinkedListNode next;
public LinkedListNode(T item)
{
data=item;
next=null;
}
}
class LinkedList<T>
{
private LinkedListNode head;
public void add(T item)
{
LinkedListNode newNode=new LinkedListNode(item);
LinkedListNode tempHead=head;
while(tempHead!=null&&tempHead.next!=null)
{
tempHead=tempHead.next;
}
if(tempHead==null)
{
head=newNode;
}
else
{
tempHead.next=newNode;
}
}
public void delete() throws Exception
{
if(head==null)
{
throw new Exception("linked list is empty");
}
LinkedListNode tempHead=head;
while(tempHead!=null&&tempHead.next!=null&&tempHead.next.next!=null)
{
tempHead=tempHead.next;
}
if(tempHead.next==null)
{
head=null;
}
else
{
tempHead.next=null;
}
}
public void printLinkedList() throws Exception
{
if(head==null)
{
throw new Exception("linked list is empty");
}
LinkedListNode tempHead=head;
System.out.println("============LinkedList printing - starts===========");
while(tempHead!=null)
{
System.out.print(tempHead.data+"\t");
tempHead=tempHead.next;
}
System.out.println("");
System.out.println("============LinkedList printing - ends===========");
}
}