Redirecting to
NADOS


  Prev   Next

Add First in a Linked List







If we wish to count lines of code, we should not regard them as "lines produced" rather the "lines spent".
~ Edsgar Dijkstra

Add First in a Linked List

Welcome back, dear reader. So, how is it going? Hope you are enjoying and understanding the linked list data structure. Let's discuss this problem. The problem is called ADD FIRST IN LINKED LIST.

Important Links : Problem Link Question Video, Solution Video

Problem Discussion :

We have to complete the body of the addFirst() function which adds a node at the beginning of a linked list. We also need to take care that the head and tail of the linked list and the size of the linked list are modified accordingly. For instance:

img

We have a linked list as shown above. We want to add 5 to the head of this linked list. So, the linked list will now have a new node at its head with a value=5. Also, the size of the linked list will be modified and the address of head will also be modified in the linked list summary object. The modified linked list after addition of the node at its head is shown below:

img

You may refer to the question video if you have any doubts regarding the question. Now, let's start our discussion.

Approach :
When the Linked List is Empty:

Let us say that we have an empty linked list i.e. there is no element currently in the linked list. We want to add the first element to this list. So, it is obvious that this element will be added to the head of the list only. Now, what is the procedure for adding a node at the beginning of an empty list? Let us try to add 10 to an empty linked list. Have a look at the diagram given below:

img

So, first of all, we will create a new node which will be inserted in the linked list. So, a memory is created for this node as shown in the figure (we have assigned a random memory address to the node.)

The second step is to insert the value into this node.

The third step is to point the head and tail variables at the newly inserted node as this node is the one and only node in the linked list. So, its starting and ending point will be the same i.e. its head and tail will point on this node only.

The fourth step is to make the next of this node point to null since it is the last node of the linked list. Also, do not forget to increase the size of the linked list by one as we have inserted an element in the list.

So, this is the simple procedure of inserting a node in an empty linked list. Now, let us move to the other situation where we will have to insert a new node to an already existing linked list.

When the Linked List is Not Empty:

Now let us say that we have the linked list as shown in the figure:

img

We want to insert 5 at the head of the linked list. So, let us understand the step by step procedure to do that:

img

The first two steps are the same where we have to create a new node and insert the value into the node.

img

In the third step, we point the next of the newly inserted node to the head of the existing linked list, so that it gets inserted before the current head and becomes the first element of the linked list.

Now that the element is inserted into the linked list successfully, we know that the head must always be at the first element of the linked list. So, we take head to t and now the insertion process is complete. Again, don't forget to increase the size of the linked list by 1 as a new element is inserted.

Now that we have understood the entire procedure for the addFirst() function, let us write the code for it.

Pseudo Code:

Create a new node and assign its data equal to the value that we want to insert. If the linked list is empty then both head and tail will be the same node and the size will be incremented. If the linked list is not empty then point the next of this new node to the head of the linked list and change the head to this node.

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 void addFirst(int val) { // write your code here Node t=new Node(); t.data=val; t.next=head; if(size==0) { tail=t; } head=t; size++; } } 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); } } else if (str.startsWith("addFirst")) { int val = Integer.parseInt(str.split(" ")[1]); list.addFirst(val); } str = br.readLine(); } } }
java; true";

So dear reader, hope that you have understood the entire procedure explained above and also understood the code. If you have any doubts regarding the solution method or the code, you may refer to the complete solution video to clear all your doubts. Now, let us discuss the time and space complexity.

Analysis:
Time Complexity:

The time complexity of the above solution is O(1) as we are just creating a new node and inserting it at the beginning of the linked list. And we are not traversing the list.

Space Complexity:

The space complexity of the above solution is O(1) as we have not used any extra memory for our work.

Hope that you have understood the time and space complexity analysis also. So, with this, we have completed this problem too.

Suggestions:

Here are some suggestions from our side that you do not want to miss:

The only suggestion that we have for you is keep practicing. There will be some problems that will be too hard to solve and some will be too easy also. So, don't get under confident or over confident in these situations. Stay calm and focus on concepts. This is the key for becoming not just a great coder, but a great problem solver.

Functions and Arrays
Strings and Linked Lists
Author: Guneet Malhotra
 
Run
Id Name