Convert A String To A Singly Linked List

Last Updated on November 16, 2022 by Prepbytes

A linked list is one of the most important topics for the interviews. Basically a linked is the link of nodes connected to every next node through a pointer and a string is defined as an array of characters ending with a special character ‘\0’. In this article, we will learn how to convert string to linked list.

Problem Statement

In this problem, we need to convert string to linked list where each node will contain a single character.

Problem Statement Understanding of how to convert string to linked list

Let’s try to understand this problem with the help of examples.

If the string given to us is “leaf”:

• Then, according to the problem statement, we have to convert string to linked list.
• The output linked list after converting the given string “leaf” to a singly linked list will be: l→e→a→f→NULL.
• While converting the string to linked list, each character in the input string will be treated as a single node of our newly created linked list.

Let’s take another example, say if the Input string: “prepbytes”

• In this case, our output singly linked list will be: p→r→e→p→b→y→t→e→s→NULL

Now, I think the problem statement is clear, so let’s see how we can approach it. Any ideas? If not, it’s okay. We will see in the next section how we can approach it.

Approach

• To convert string to linked list, the nodes of our output singly linked list will be having characters in the data field, so we will make our node class have a char variable that will store character data and a next pointer to store the next node’s address.
• Loop through the string and create the nodes while iterating through it.
• Make the last node’s next pointer NULL.

Algorithm to convert string to linked list :

1. Check if the string is empty.
• If it is empty, return a NULL pointer.
• Else, proceed ahead.
2. Create a node that will store the first character of our string, and it will be the head of our newly created list.
3. Initialize a curr pointer with the above-created node.
4. Start iterating the string from its second character till last
5. Create a new node and assign curr→next to it.
6. Update the curr pointer to the newly created node.
7. Return the head pointer

Now, we will get our desired list as output, and we could print it to check.

Dry Run to convert string to linked list

Code Implementation

#include <iostream>
using namespace std;

// class with constructor for a Singly Linked List
class node {
    public:
    char data;
    node* next;
    // constructor
    node(char x){
        data = x;
        next = NULL;
}
};

// This function converts a string to a singly linked list
node* string_to_SLL(string s)
{
    // check if the string is empty 
    if(s.size() == 0) return NULL;
    // create a head pointer as discussed in step 2
    node *head = new node(s[0]);
    // create a pointer to store the address of previously created node
    node* curr = head;

    // iterate from second character to the last character
    for (int i = 1; i < s.size(); i++) {
        // create a new node and attach it to previously created node
        curr->next = new node(s[i]);
        // update the curr pointer to newly created node
        curr = curr->next;
    }
    return head;
}

// This function is used to print the content of linked list
void print(node* head)
{
    node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " -> ";
        curr = curr->next;
    }
    cout<<"NULL";
}

// main function
int main()
{
    string s = "leaf";
    node *head = string_to_SLL(s);
    print(head);
    return 0;
}

class Node 
{
    char data;
    Node next;
    Node(char data)
    {
        this.data=data;
    }
}
public class ConvertString 
{
    public static void main(String[] args) 
    {
        String s="leaf";
        Node head=string_to_SLL(s);
        print(head);    
    }  
    static Node string_to_SLL(String s)
    {
        if(s.length()==0)
        {
            return null;
        }
        Node head=new Node(s.charAt(0));
        Node curr=head;
        for(int i=1;i<s.length();i++)
        {
            curr.next=new Node(s.charAt(i));
            curr=curr.next;
        }
        return head;
    }  
    static void print(Node head)
    {
        Node curr=head;
        while(curr!=null)
        {
            System.out.print(curr.data+" ");
            curr=curr.next;
        }
        System.out.println();
    }
}

class node:
	def __init__(self):
		data = None
		next = None

def add(data):

	newnode = node()
	newnode.data = data
	newnode.next = None
	return newnode

# This function converts a string to a singly linked list
def string_to_SLL(text,head):

	head = add(text[0])
	curr = head

	# curr pointer points to the current node
	# where the insertion should take place
	for i in range(len(text) - 1):
	
		curr.next = add(text[i + 1])
		curr = curr.next
	
	return head

# This function is used to print the content of linked list
def print_(head):

	curr = head
	while (curr != None) :
	
		print ((curr.data), end = " - > " )
		curr = curr.next
	
text = "leaf"
head = None
head = string_to_SLL(text, head)
print_(head)

Output

l→e→a→f→NULL

Time complexity: O(n), Where n is the number of characters in the string.
Space Complexity: O(n), as we are creating a singly linked list having n nodes.

So, in this article, we have tried to explain how to convert a string to linked list.If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.ode.prepbytes.com/interview-coding/practice/linked-list).

FAQs

1. What is a linked list?

The linked list is a set of nodes in which each node has a pointer to the next node.

2. How do I convert the linked list into strings in Java?

We can use StringBuffer or StringBuilder to convert to linked list in java.

3. Why do we use a linked list?

Linked lists can be used to implement stacks, queues, and other abstract data types and are also used for their efficient insertion and deletion.