Convert A String To A Singly Linked List

Approach

We will be following the simple brute force approach to solving this problem. We will traverse the entire string and will be creating new nodes of the linked list, with the value being the value of the current index position of the string. 

Eg: Let’s consider a string s = “coding”. Return the head pointer of the linked list, generated by the elements of the string s.

So here, we will be constructing a linked list of the characters of strings. 

We will be iterating over the characters of the string and will be creating a new node of a linked list accordingly. 

Returning the head pointer of the linked list gives us the answer.

Algorithm

Let’s look at how we will be performing the above conversion:

• First, create a class or struct node, which represents the node of the linked list. It should have 2 attributes, mainly data (containing the value of the node) and the next (containing the address of the next node of the linked list). 
• Now iterate over the string, and create a new node of the linked list with the corresponding character of the string. 
• Keep a temporary head pointer, namely temp, which shall be pointing to the last element of the linked list every time. This helps in inserting a new node to a linked list with O(1) time complexity. 
• Insert a new element next to temp, and make temp = temp.next, i.e changing the value of temp to the newly added element, which is the last element. 
• On reaching the end of the string, we have successfully constructed a linked list from this string. Now return the head pointer of the linked list. 

Dry Run

Let us try to run the above approach via an example for better understanding and purposes.

Input:

s = “coding”

Output:

c -> o -> d -> i -> n ->g

Return the head pointer of the linked list.

Explanation:

s = “coding”

Step 1: Iterate over the string “coding”, and create a new node every time. 

Step 2: First comes the character “c”, so we create a new node of linked list with data set to “c”, and next set to null.

Step 3: Set temp = node, i.e point the temp variable to this newly created node. 

Step 4: Now the next character “o”, comes, so we create a new node of the linked list with data = “o”, and next = null.

Step 5: Set temp.next = node i.e set temp’s next attribute to store this newly created node’s address.

Step 6: Set temp = temp.next, now temp points to this new node, which is “o”. 

Step 7: Continue until the string is finished. 

Implementation in Python

class Node:
# definition of node of linked list

    def __init__(self, data: str = "", next=None) -> None:
        self.data = data
        self.next = next


def convert_to_linked_list(s: str) -> Node:
    """
        converts a string to a linked list
        returns the head of the linked list
    """
    head = Node(s[0])
    temp = head

    for char in s[1:]:
        node=Node(char)
        temp.next = node
        temp = temp.next

    return head

# driver code
s = "coding"
print("Enter the string: " + s)

if(s == "" or s == " "):
    print("String is empty")
    exit()
    
head = convert_to_linked_list(s)

# displays the linked list
while head:
   print(head.data,end=" -> ")
   head = head.next
print()

You can also try this code with Online Python Compiler

Run Code

Output 

Implementation in C++

#include <bits/stdc++.h>
#define ll long long int
using namespace std;

struct node
{
   // definition of the node of linked list
   string data;
   node *next;
};

int main()
{
   // input
   string s = "coding";
   cout << "Enter string: " + s << endl;
   
   if(s == "" || s == " "){
       cout << "String is empty" << endl;
       return 0;
   }

   // creates a head with the value being
   // the first element of string
   
   node *head = new node();
   head->data = s[0];
   
   // temporary variable for iterating
   node *temp = head;

   // iterating over the rest of string
   for (int i = 1; i < s.length(); i++)
   {
       // creating nodes at every point
       node *curr = new node();
       
       curr->data = s[i];
       temp->next = curr;
       temp = temp->next;
   }

   // displaying the linked list
   while (head != NULL)
   {
       cout << head->data << " -> ";
       head = head->next;
   }
   cout << endl;
   return 0;
}

You can also try this code with Online C++ Compiler

Run Code

Output

Implementation in Java

class node {
// definition of the node of linked list

   char data;
   node next;
}

class Main {
   public static void main(String[] args) {

       // input

       String s = "coding";
       System.out.println("Enter the string: " + s);
       
       if(s == "" || s == " "){
           System.out.println("String is empty");
           return;
       }
       
       // creates a head node with first char of string as value
		
       node head = new node();
       head.data = s.charAt(0);
       node temp = head;
		
       // iterates over the rest of the string
       for (int i = 1; i < s.length(); i++) {

           // creates a node at every instant
           node curr = new node();
           
           curr.data = s.charAt(i);
           temp.next = curr;
           temp = temp.next;

       }
       // displays the linked list
       while (head != null) {
           System.out.print(head.data + " -> ");
           head = head.next;
       }
       System.out.println();
       return;
   }
}

You can also try this code with Online Java Compiler

Run Code

Output

Complexity Analysis

Time Complexity: We will be iterating over the entire string to create a new node and create a singly linked list, so our time complexity reaches O(n), where n is the length of the string we are iterating over.

Space Complexity: We are creating a linked list of n nodes, where n is the length of the string, so our space complexity also reaches O(n). 

Frequently Asked Questions

What is a linked list?

A linked list is a linear data structure where elements are nodes of the linked list. Each node has its attributes defined. Usually, in a linked list, the node consists of data, which contains the value of the node, and next, which contains the address of the next node.

What are the different types of linked lists present?

There are different types of linked lists present, like Singly Linked Lists, Doubly Linked Lists, Circular Linked Lists, and Doubly Circular Linked Lists.

How is Singly Linked List different from Doubly Linked List?

The nodes of the singly linked list contain only two attributes, data, and next, whereas the nodes of the doubly linked list contain three attributes, data, next, and prev, where prev contains the address of the previous node, and next contains the address of the next node. 

What is a String?

A String is a datatype, which stores the information within “ “ (double quotes). These can also be termed an array of characters.

What is String Slicing? 

String Slicing refers to the process of obtaining a sub-string from a string via the start and end index of the original string. 

Conclusion

So, Ninjas, we hope after reading this, you are now more familiar with the linked list and various operations performed on it, like insertion and displaying the output. We created a new linked list from the values given in the string. 

Check out the Coding Ninjas Studio library to get a better hold of the data structures and algorithms.

Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

Recommended Reading:

• Advantages and Disadvantages of Linked List
• Singly Linked List v/s Doubly Linked List
• Compare two strings represented as Linked Lists
• Check if a Linked List of strings forms a palindrome
• Insert a Node at a Specific Position in a Linked List
• Check if a Linked List is Palindrome or not.
• Swap Nodes in Pairs
• Top String Coding Interview Questions
• Problems on Linked Lists
• Doubly Linked List

Recommended problems -

• Beautiful String
• Subsequence of a String
• Find the Shortest Substring in a String

Do check out the Interview guide for Product Based Companies as well as some of the popular interview problems from top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, and System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.