Redirecting to
NADOS


  Prev   Next

Get Value in Linked List







A little progress each day adds up to big results.
~ Satya Nani

Get Value in Linked List

Welcome back readers!

We hope that the different functions of Linked List that we discussed lately are clear to you. I'm pretty sure that you found those functions quite easy to understand and code.

In this article also we will discuss another Linked List function that is 'Get Value' as it's quite clear from the name of the function that we need to get a particular value of the linked list. We will look at different possibilities while coding it.

Let's jump to the problem.

Important Links : Question Video, Solution Video

Problem Discussion :

Just like previous problems you are given a partially written LinkedList class.

Here is a list of existing functions:

  1. addLast - adds a new element with given value to the end of Linked List
  2. display - Prints the elements of a linked list from front to end in a single line. All elements are separated by space.
  3. size -Returns the number of elements in the linked list.
  4. removeFirst - Removes the first element from Linked List.

You are required to complete the body of getFirst, getLast and getAt function.

  • getFirst - Should return the data of the first element. If empty should return -1 and print "List is empty".
  • getLast - Should return the data of the last element. If empty should return -1 and print "List is empty".
  • getAt - Should return the data of elements available at the index passed. If empty should return -1 and print "List is empty". If invalid index is passed, it should return -1 and print "Invalid arguments".

Input and Output are already managed for you.

So, friend, I hope that question is clear to you. But if you still face any difficulty in understanding this then please check out our question video where our team has particularly explained what needs to be done in this question. So that you can get some hint of the problem and give it a fair try.

Approach :

If you have read the above mentioned points regarding what you are required to do and understand them then trust me if we will just follow these steps as it is and we will be done with our problem. Let's talk about each function in detail.

getFirst

Time Complexity: O(1)

Space Complexity: O(1)

What does this function say? It says that it should return the data of the first element. If empty should return -1 and print "List is empty".

We literally just need to tackle these two points.

  • return the data of first element:
    The first element of Linked List can be accessed using keyword head.data, where head points towards the first element's address and .data helps to access the value at the address.
    img
  • If empty should return -1 and print "List is empty":
    It is possible that the given Linked List is empty which implies that the size of the Linked List is 0. So before simply accessing the head of Linked List, it is important that you check this using an "if" condition, whether the size is 0 or not.
    If it is 0, then you need to print "List is empty" and return -1 as mentioned in the question.
    Else you can return head.data.
    img
getLast

Time Complexity: O(1)

Space Complexity: O(1)

What does this function say? It says that it should return the data of the last element. If empty should return -1 and print "List is empty".

Doesn't this statement look similar to the previous one?

Yes, it's similar. The only difference is "last" instead of "first". Let's look at it.

We literally just need to tackle these two points like before.

  • return the data of last element:
    The last element of Linked List can be accessed using keyword tail.data, where tail points towards the last element's address and .data helps to access the value at the address.
    img
  • If empty should return -1 and print "List is empty":
    It is possible that the given Linked List is empty which implies that the size of Linked List is 0. So before simply accessing the head of Linked List, it is important that you check this using an "if" condition, whether the size is 0 or not.
    If it is 0, then you need to print "List is empty" and return -1 as mentioned in the question.
    Else you can return tail.data.
    img
getAt

Time Complexity: O(n)

Space Complexity: O(1)

What does this function say? It says that it should return the data of elements available at the index passed. If empty should return -1 and print "List is empty". If invalid index is passed, it should return -1 and print "Invalid arguments".

Let's handle these conditions one by one.

  • return the data of element available at the index passed: To access the data of elements present at index passed, we need to define a node, temp with address of head then apply a for loop, initializing with 0 to one less than given index.
    Then we update temp with temp.next which at i = 0, points towards the address of element at index 1.
    That's the reason we set the limit of for loop till one less than the index. So that for index = 5, loop runs till i = 4 but temp points towards the address of the 5th index element.
    After exiting the for loop, our temp points toward the address of the element, of which we need to return data.
    So at this point we simply return temp.data.
    img
  • If empty should return -1 and print "List is empty":
    It is possible that the given Linked List is empty which implies that the size of Linked List is 0. So before simply accessing the head of Linked List, it is important that you check this using an 'if' condition, whether the size is 0 or not.
    If it is 0, then you need to print "List is empty" and return -1 as mentioned in the question.
    Else you can return the data at a given index with the help of steps discussed above.
    img
  • If invalid index is passed, should return -1 and print "Invalid arguments":
    It is also possible that the index which the user passes is an invalid index. An invalid index is defined if the index is not in the range of 0 to size -1 that means either the index is smaller than 0 or greater than or equal to size.
    Before taking the control to for loop it is necessary that you check this using an "if" condition.
    If the index is either smaller than 0 or greater than or equal to size then we print "" and return -1.
    img

Yes! We are done with all the three different functions that return us value according to their use.

import java.io.*; import java.util.*; public class Main { public static class Node { int data; Node next; } public static class LinkedList { Node head; Node tail; int size; void addLast(int val) { Node temp = new Node(); temp.data = val; temp.next = null; if (size == 0) { head = tail = temp; } else { tail.next = temp; tail = temp; } size++; } public int size(){ return size; } public void display(){ for(Node temp = head; temp != null; temp = temp.next){ System.out.print(temp.data + " "); } System.out.println(); } public void removeFirst(){ if(size == 0){ System.out.println("List is empty"); } else if(size == 1){ head = tail = null; size = 0; } else { head = head.next; size--; } } public int getFirst(){ if(size == 0){ System.out.println("List is empty"); return -1; } else { return head.data; } } public int getLast(){ if(size == 0){ System.out.println("List is empty"); return -1; } else { return tail.data; } } public int getAt(int idx){ if(size == 0){ System.out.println("List is empty"); return -1; } else if(idx < 0 || idx >= size){ System.out.println("Invalid arguments"); return -1; } else { Node temp = head; for(int i = 0; i < idx; i++){ temp = temp.next; } return temp.data; } } } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); LinkedList list = new LinkedList(); String str = br.readLine(); while(str.equals("quit") == false){ if(str.startsWith("addLast")){ int val = Integer.parseInt(str.split(" ")[1]); list.addLast(val); } else if(str.startsWith("size")){ System.out.println(list.size()); } else if(str.startsWith("display")){ list.display(); } else if(str.startsWith("removeFirst")){ list.removeFirst(); } else if(str.startsWith("getFirst")){ int val = list.getFirst(); if(val != -1){ System.out.println(val); } } else if(str.startsWith("getLast")){ int val = list.getLast(); if(val != -1){ System.out.println(val); } } else if(str.startsWith("getAt")){ int idx = Integer.parseInt(str.split(" ")[1]); int val = list.getAt(idx); if(val != -1){ System.out.println(val); } } str = br.readLine(); } } }
java; true";

That was easy. Wasn't it?

Our desire to make you learn will remain unsatisfactory if you still have doubts. We strongly recommend you to watch our video lecture on Get Value for clearing any type of doubts.

Suggestions and feedback are always welcomed. You can contact us via our website.

All the best for a bright future!

Happy Coding!

Linked List
Node
Author: Nikita Aggarwal
 
Run
Id Name