Welcome back, dear reader. So, how is it going? We hope you have got a basic idea of the linked list data structure. So, let's discuss this problem.
Important Links :Question Video, Solution Video
Prev Next
Display a Linked List
Problem Discussion :
We have to display a linked list and we also have to complete the size function of the linked list. You may refer to the question video if you have any doubts regarding the question. So, let's get started.
Approach :
Consider the linked list shown below:
The linked list has its head at address 5k and its tail at address 9k. (These are random addresses just to depict that each node has an address.) Now, we need to write the size() function and the display() function for the linked list. We recommend you try to solve this question yourself and then move on to the solution.
Size: Well if you notice, the linked list class that we have created already has a size data member in it. Also, when we add an element to the end of the linked list using the addLast() function, we increment the size value. So, the size value is maintained throughout the creation of the linked list as well as during the insertion of the nodes at the end of the list. So, the size data member already contains the size of the linked list. So, we just have to return it.
So, hope that this is clear to you. Now, let us move forward with the display function.
Display: The first question is how we want to display the elements of the linked list. Well, we want space-separated elements to be displayed in a single line. Now, look at the diagram given below:
To display the linked list we take a temporary Node type of variable "t" at the head of the linked list. In the call stack, we have shown the memory allocated to the linked list summary object. After that the variable t stores the address of the head node i.e. 5k. Now let us discuss the procedure:
- We will check the value of t. If the value of t is not null, we will print the data stored in the node at which t resides.
- After printing the data of the current node, we will go to the next node by assigning t's next to t i.e. t=t.next.
- We will keep on doing this until we reach the end of the linked list. The linked list will end when t does not contain the address of any node i.e. when t=null.
The above-mentioned steps are applied and the traversal of the linked list is shown below:
The linked list is displayed by applying the above-mentioned procedure step by step as shown in the above diagrams. When t is at the head it has a value of the address of the head i.e. 5k. So, it prints t.data which is the data of the node at which t resides and that is 10. After this, we move t to its next by doing t=t.next. So, the value of t changes from 5k to 6k as shown in the figure. So, the data at address 6k i.e. 20 gets printed. We follow the same procedure and finally, we reach the last element i.e. t=9k. We print the data and move to t.next i.e. t becomes null. This is where we have to stop and our linked list is completely displayed.
You may refer to the solution video to understand the above procedure if you have any doubts about it. So, now that we know the procedure, let's write the code.
Pseudo Code
- Keep a variable of type node (p) at the head of the Linked List
- Display the data of the node (p) is present at and move p to its next i.e. p=p.next.
- Keep up this procedure till we reach the tail. After printing the data of the tail, exit the procedure.
- To calculate the size, repeat the same procedure but don't print the nodes, rather count them and return the count at the end.
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 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();
}
str = br.readLine();
}
}
}
java;
true";
Now, let us discuss the time and space complexity of the above methods.
Analysis
Time Complexity:
- Size: The time complexity of the size method is O(1) as we are just returning the size of the linked list.
- Display: The time complexity of display is O(n) as we are traversing the entire linked list of n elements.
Space Complexity:
The space complexity of the above methods is O(1) as we have not used any extra space for any of the above methods.
So, dear reader, we hope that you understood the above methods and the code completely and also understood the time and space complexity analysis. If you still have any doubts, you may refer to the complete solution video to clear them.
Suggestions:
Here are some suggestions from our side that you don't want to miss:
- These questions are not to test your knowledge rather they are to build it. So, just learn by reading the articles or watching the videos as we are in that phase of learning a linked list where we are learning the basic traversal and display operations of the linked list.
