Convert A String To A Singly Linked List

Introduction

Linked list, as well as the string, is an important concept to learn. A linked list is a collection of nodes where each node is connected to the next node through its pointer whereas a string is an array of characters. This problem will cover a basic understanding of the linked list and string. Here we will first discuss the approach to solve this problem and then implement the solution in C++.

Problem Statement

Given a string, you need to convert the string into a singly linked list where each node will contain a single character.

Input:

“linkedlist” (string)

Output:

l→i→n→k→e→d→l→i→s→t→NULL

Method

First, we will define the node of the singly linked list where there will be a char variable as a data field and a node pointer to store the address of the next node of the linked list.

For converting the string to a linked list first, we will iterate through each character of the given string and create the node for each character of the string while iterating through it.

Algorithm

• First, check if the string is empty or not. If empty, return a null pointer.

• Otherwise, create a node that will store the first character of the given string; it will be the head of the linked list and initialize the tmp pointer with the address of the head node.

• Then start iterating from the second character and create a node for each character; store the address of the newly created node in tmp→next and move tmp pointer to the newly created node.

• At the end return the head pointer of the linked list created from the string.

// function to convert a String To A Singly Linked List

 node* covertStringToLL(string s)
{
  // check if the string is empty 
    if(s.size() == 0) return NULL;
    
  node* head;
  
  node* tmp=new node(s[0]); // pointer to store the address of starting node of the linked list
  
  head=tmp;
  
  // interating for creating node from next characters
  for(int i=k;i<s.size();k++)
  {
  //create a new node and link it to previously created node
  tmp->next= new node(s[k]);
  
  // update the tmp pointer to newly created node
  tmp=tmp->next;
}

return head;
 
}

Code

// c++ code for converting a String To A Singly Linked List

#include<bits/stdc++.h>
using namespace std;


class node{

public:
char data;
node* next;

//constructor
node(char c)
{
data=c;
next=NULL;
}

};

// function to convert a String To A Singly Linked List

node* covertStringToLL(string s)
{
  // check if the string is empty 
    if(s.size() == 0) return NULL;
    
  node* head;
  
  node* tmp=new node(s[0]); // pointer to store the address of starting node of the linked list
  
  head=tmp;
  
  // interating for creating node from next characters
  for(int k=1;i<s.size();k++)
  {
  //create a new node and link it to previously created node
  tmp->next= new node(s[k]);
  
   // update the tmp pointer to newly created node
  tmp=tmp->next;
}

return head;
 
}
 
 //  function to print the linked list
void print(node* head)
{
    node* curr = head;
    while (curr != NULL) {
        cout << curr->data << " -> ";
        curr = curr->next;
    }
    cout<<"NULL";
}
 
 // driver code
 int main()
{
    string s = "linkedlist";
    node *head = covertStringToLL(s);
    print(head);
    return 0;
}
 

Output

Complexity Analysis

For the above algorithm, the time complexity is O(n), where n is the number of characters in the string.

As we have created a singly linked list with n nodes, space complexity is also O(n).

FAQs

 1). What is a linked list?

A linked list is a dynamic data structure where each element (called a node) is made up of two items: the data and a reference (or pointer), which points to the next node. A linked list is a collection of nodes where each node is connected to the next node through its pointer.

 2). How many types of linked lists are there?

There are mainly four types of linked lists.

                Singly linked list

                Doubly linked list

                Circular linked list

                Doubly Circular linked list

3). Application of singly linked list?

A singly linked list is a unidirectional linked list; that can be traversed in only one direction from head to the last node (tail).

• It is used to implement stack and queue data structures.

• To prevent the collision between the data in the hash map, we use a singly linked list.

• In notepad, it also uses the singly linked list for performing undo or redo or deleting functions.

Key Takeaways

This article covered how to convert a string to a singly linked list. Having a good hold on data structure like Linked List can be a huge plus point in a coding interview.

Check out the CodeStudio library for getting 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 CodeStudio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning!