Get Value In Linked List

Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

1. You are given a partially written LinkedList class.
2. Here is a list of existing functions:
2.1 addLast - adds a new element with given value to the end of Linked List
2.2. display - Prints the elements of linked list from front to end in a single line.
All elements are separated by space.
2.3. size - Returns the number of elements in the linked list.
2.4. removeFirst - Removes the first element from Linked List.
3. You are required to complete the body of getFirst, getLast and getAt function
3.1. getFirst - Should return the data of first element. If empty should return -1 and print "List is empty".
3.2. getLast - Should return the data of last element. If empty should return -1 and print "List is empty".
3.3. getAt - Should return the data of element available at the index passed. If empty should return -1 and print "List is empty". If invalid index is passed, should return -1 and print "Invalid arguments".
4. Input and Output is managed for you.
Input Format
Input is managed for you
Output Format
Output is managed for you
Question Video
Constraints
None
Sample Input
addLast 10
getFirst
addLast 20
addLast 30
getFirst
getLast
getAt 1
addLast 40
getLast
addLast 50
removeFirst
getFirst
removeFirst
removeFirst
getAt 3
removeFirst
removeFirst
getFirst
quit
Sample Output
10
10
30
20
40
20
Invalid arguments
List is empty


  • Editorial

    Get First

    The problem deals with retrieving the first node data from the linked list. The problem can be in one of the two cases:

    1. Size != 0

    This implies that our list is not empty so in that case we simply need to return the data present at our head node.

    2. Size == 0

    This is the case when our list is empty which implies that there are no nodes in our list, in that case, we can not return any relevant data so we prompt an error message displaying "List is empty" and return -1 as a default value.

    Below is the implementation in Java:

    public int getFirst() {
                                        if (size == 0) {
                                        System.out.println("List is empty");
                                        return -1;
                                        } else {
                                        return head.data;
                                        }
                                    }

    java false

    Time Complexity: O(1)

    The time complexity for the function is constant as we only need to return the data present at our head node.

    Space Complexity: O(1)

    The space complexity for the function is constant as we have not used any extra space for our algorithm.

    Get Last

    The problem deals with retrieving the last node data from the linked list. The problem can be in one of the two cases:

    1. Size != 0

    This implies that our list is not empty so in that case we simply need to return the data present at our tail node.

    2. Size == 0

    This is the case when our list is empty which implies that there are no nodes in our list, in that case, we can not return any relevant data so we prompt an error message displaying "List is empty" and return -1 as a default value.

    Below is the implementation in Java:

    public int getLast() {
                                        if (size == 0) {
                                        System.out.println("List is empty");
                                        return -1;
                                        } else {
                                        return tail.data;
                                        }
                                    }

    java false

    Time Complexity: O(1)

    The time complexity for the function is constant as we only need to return the data present at our tail node.

    Space Complexity: O(1)

    The space complexity for the function is constant as we have not used any extra space for our algorithm.

    Get At

    The problem deals with retrieving the node data at the desired index from the linked list. The problem can be in one of the two cases:

    1. Size != 0 (General Case)

    This implies that our list is not empty so in that case, we need to traverse to the desired index and then return the value. To achieve this we will take a temporary variable initialized with head pointer and then iterate it to reach the desired node and then return with the data at the current node.

    2. Size == 0

    This is the case when our list is empty which implies that there are no nodes in our list, in that case, we can not return any relevant data so we prompt an error message displaying "List is empty" and return -1 as a default value.

    3. If index < 0 || index >= size

    This is the case when our input parameter is out of range as our index parameter can have values from 0 <= index < size to satisfy 0 based indexing in programming. So in this case we will prompt an error message "Invalid Arguments." and return 1 as the default value.

    Below is the implementation in Java:

    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;
                                        }
                                    }

    java false

    Time Complexity: O(n)

    The time complexity for the function is linear as we are traversing over the linked list to reach the desired index which is dependent on the length of the linked list.

    Space Complexity: O(1)

    The space complexity for the function is constant as we have only used a temporary variable for our algorithm.

  • Asked in Companies
  • Related Topics






Video Solution

Code Solution

Run
 
Run
Id Name