Taking linked list input from a user is a common requirement in many programming problems and assignments. A linked list is a linear data structure that consists of nodes where each node contains data and a pointer to the next node. To take a linked list as input from the user, we need to take each node’s data and link it to the next node. In this article, we will learn how to take linked list input from the user in C/C++ and Java.
Prerequisites
Before we dive into the steps to take linked list input, let’s first understand the prerequisites:
- Basic knowledge of linked list data structure
- Understanding of node structure containing data and next pointer
- Ability to create nodes dynamically and link them
- Knowledge of taking input from user in respective language (C/C++/Java)
As a prerequisite, you must have a basic understanding of how linked lists work. You should know that a linked list contains nodes where each node points to the next node. This pointing is done using a next pointer in each node. Typically, a node structure contains a data part and a next pointer. Something like:
struct Node{ int data; Node* next; };
You should also know how to dynamically allocate nodes in C/C++ and Java. Dynamic allocation allows us to create nodes on the fly as we take input from the user.
Steps to take Linked List input in C/C++
Let’s now look at the step-by-step process to take linked list input from the user in C/C++:
- Ask the user for the number of nodes (n) in the linked list
- Create a Node pointer head initialized to NULL which will serve as the head of the linked list
- Iterate from 0 to n-1 using a loop
- Dynamically allocate a new Node using malloc() and initialize next as NULL
- Take the node’s data input from the user
- If head is NULL, assign newly created node to head
- Else, link current node’s next to head and update head to current node
- Return head pointer containing the linked list
The above steps dynamically create n nodes by taking input from the user and link each node together to form a linked list. Let’s implement the above logic in C code:
Node* takeInput(){ int n; cin >> n; Node* head = NULL; for(int i = 0; i < n; i++){ Node* newNode = (Node*)malloc(sizeof(Node)); newNode->next = NULL; cin >> newNode->data; if(head == NULL){ head = newNode; } else{ newNode->next = head; head = newNode; } } return head; }
We first take the number of nodes as input and initialize a head pointer. Then we iterate n times, create a new node dynamically, take the data input, and link this node appropriately. The head pointer gets updated whenever a new node is added. Finally, the head pointing to the first node of the linked list is returned.
Steps for taking Linked List input in Java
The process of taking linked list input in Java is similar to C/C++. The key steps are:
- Ask for number of nodes n
- Create a Node class with data and next as members
- Create a head node initialized as null
- Iterate n times
- Create a new Node using new keyword
- Set next as null
- Take node’s data input
- If head is null, assign new node to head
- Else, link new node’s next to head and make new node as head
- Return head node
And here is the Java implementation:
public Node takeInput(){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Node head = null; while(n-- > 0){ Node newNode = new Node(); newNode.next = null; newNode.data = sc.nextInt(); if(head == null){ head = newNode; } else{ newNode.next = head; head = newNode; } } return head; } class Node{ int data; Node next; }
This follows the exact same logic as the C/C++ implementation. The only differences are using the Scanner class for input and explicitly creating the Node class in Java.
Handling other Inputs
So far we have taken integer inputs in the linked list. To take other data types as input, we simply need to change the datatype of the data part of the node. For example:
// For float struct Node{ float data; Node* next; }; // For string struct Node{ string data; Node* next; };
Similarly, in Java, we can use Float, String or any other datatype as the data member in the Node class.
The remaining logic of taking input remains exactly same. This allows the linked list to store different data types as per need.
Taking linked list input with tail pointer
In the above implementations, we only maintained a head pointer to the linked list. We can also maintain a tail pointer to make insertion efficient. The steps will be:
- Take number of nodes as input – n
- Create head and tail pointers initialized as null
- Iterate n times
- Create new node and initialize next as null
- Take node data input
- If head is null, set head and tail as new node
- Else, set current tail’s next as new node and update tail as new node
- Return head and tail pointers
Maintaining the tail pointer avoids traversing the linked list from head to find the current tail for insertion.
Validity Checks
While taking linked list input, we should also perform some validity checks:
- Check if number of nodes entered is non-negative
- Check if data entered for each node is valid
- Print error and exit if invalid input
For example, we should check if the user enters a negative number of nodes or invalid data like string for an integer data typed linked list.
These checks make the program more robust and user-friendly.
Conclusion
To summarize, taking linked list input involves dynamically creating nodes, linking them appropriately and returning head (and tail) pointer. We iterate based on number of nodes and take each node’s data. C and Java implement the same logic with minor syntactical differences. Insertion at head simplifies input. We can store different data types by changing the node data part’s datatype. Some validity checks are required for robustness.
The key things to remember are:
- Know prerequisites like node structure, dynamic creation, linking nodes
- Take number of nodes as input n
- Iterate n times creating a new node in each iteration
- Take node data input from user
- Link nodes by updating head (and tail) pointers appropriately
- Perform validity checks on number of nodes and data values
- Return head (and tail) pointers
With this we can take linked list input from the user in C/C++ and Java. This input method is essential for many linked list based problems and assignments.
Sample Code
Here is the complete sample code for taking linked list input in C/C++:
#includeusing namespace std; struct Node{ int data; Node* next; }; Node* takeInput(){ int n; cin >> n; Node* head = NULL; Node* tail = NULL; for(int i = 0; i < n; i++){ Node* newNode = new Node(); cin >> newNode->data; newNode->next = NULL; if(head == NULL){ head = newNode; tail = newNode; } else{ tail->next = newNode; tail = newNode; } } return head; } int main() { Node* head = takeInput(); Node* temp = head; while(temp != NULL){ cout << temp->data << " "; temp = temp->next; } }
And here is the Java sample code to take linked list input:
import java.util.*; class Main{ public static Node takeInput(){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); Node head = null; Node tail = null; while(n-- > 0){ Node newNode = new Node(); newNode.data = sc.nextInt(); newNode.next = null; if(head == null){ head = newNode; tail = newNode; } else{ tail.next = newNode; tail = newNode; } } return head; } public static void main(String args[]){ Node head = takeInput(); Node curr = head; while(curr != null){ System.out.print(curr.data + " "); curr = curr.next; } } } class Node{ int data; Node next; }
These implement the complete logic of taking linked list input that we discussed. You can modify them as required for your program.
Practice Questions
Here are some practice questions on taking linked list input:
- Take input of a linked list and print reverse of it.
- Take input of a integer linked list and segregate even and odd nodes in seperate lists.
- Take input of a linked list and print its length.
- Take input of a linked list and find the largest element in the linked list.
- Take input of a linked list and split it into two linked lists – one for odd positioned nodes and one for even positioned nodes.
Solving such questions will help you get better at taking linked list input from the user.
Frequently Asked Questions
Here are some common FAQs on taking linked list input:
Why do we insert at head while taking input?
Inserting at head simplifies linking of nodes while taking input. We don’t need to traverse the existing list to find the tail. Just update the head pointer.
How do we take input in linked lists in languages other than C/C++/Java?
The general logic remains same across languages. Just use appropriate syntax for dynamic node creation and linking in that language.
Can we take input by inserting at tail instead of head?
Yes, it is possible. We will have to maintain tail pointer as well to avoid traversing from head each time.
What if we want to take input of a sorted linked list?
In case of sorted linked list input, we will have to insert each new node in sorted order instead of just inserting at head.
How do we take input in circular and doubly linked lists?
The only additional step is to make next of last node point to first node in case of circular linked list. For doubly linked list, we also take prev pointer handling.
Conclusion
Taking linked list input from the user is an essential skill for programming linked list based problems. We learned how to take input in C/C++ and Java by dynamically creating nodes and linking them. Validation of inputs is important. Practice questions will help get better at applying the input logic. This forms a good foundation for solving further linked list problems.