Implementation of Index based Linked List

In previous post, we saw the implementations of different add and remove functionality in linked list. This post is about implementation of index based linked list. We have seen the introduction, of linked list.Linked list is a linear data structure whose order is not given by the physical location of object. Data stored at non-contiguous memory locations , so we can not get the elements of linked list by passing the position.Refer the below graphical explanation.

Since , there is no fixed pattern for consecutive object memory location , indexing is not possible in linked list.That’s why accessing the elements in linked list is costly operation.But still we can access the elements by position in linked list through traversing the entire linked list.We are going to implement below two methods in linked list.[Try Yourself]

get(int index) : This method will return the object at particular position by traversing the linked list in forward direction. In Doubly Linked list we can traverse the list in both forward and backward direction based on index.Valid Index starts from 0 and ends on (N-1) , where N=size of linked list.

Steps:

  1. if index=0 , return the data at root node.
  2. if index=sizeof list – 1 , then return the data at last node.
  3. if 0 < index < sizeof list – 1 , traverse through each node and increment the pointer by 1. If pointer value and index value matches, return the data from pointer node.

indexOf(T data) : This method will return the position of data in linked list from root node if data present in linked list otherwise it will return -1. If linked list has duplicate data, then it will return the position of first occurrence of  data in forward direction.

Steps:

  1. Start with root node as pointer node and initialize index with 0;
  2. If  pointer node data equal to input data , then return the index value.
  3. If pointer node data is not equal to input data, increment index by one and update pointer node as next node.
  4. Continue the steps 2 and 3 end of the linked list.
  5. If data not found in linked list , return -1.

 

 

Output:

****** ADDING DUPLICATE Item TO END OF THE LINKED LIST ******
AFTER ADDING ALL ITEMS , size: 6 [Item [itemId=104, itemName=Samsung Pro, price=300.0],Item [itemId=101, itemName=IPhone-5S, price=200.0],Item [itemId=105, itemName=Samsung Pro Plus, price=500.0],Item [itemId=102, itemName=IPhone-6S, price=500.0],Item [itemId=103, itemName=IPhone-XX, price=1000.0],Item [itemId=101, itemName=IPhone-5S, price=200.0]]

Item at position 0 :Item [itemId=104, itemName=Samsung Pro, price=300.0]
Item at position 2 :Item [itemId=105, itemName=Samsung Pro Plus, price=500.0]

Position of IPhone-5S:1
Position of Samsung Pro:0

————————————————————————————————–

Hope you like this post. Please give your valuable suggestions/comments.

In next post, we will see how to reverse the linked list.

 

You may like –

Top