 New update is available. Click here to update.
Last Updated: Jun 30, 2023
Medium

# Convert A String To A Singly Linked List

## Introduction

Hello Ninjas!! How excited are you when it comes to converting a data type to a data structure? Yes, here we’ll be converting a linked list to a string. In this blog, we shall be converting a string to a linked list. Are you ready for it? If you are not familiar with a linked list and strings, then here’s a brief intro.

Linked List is a linear data structure where the elements are not stored in contiguous memory locations. A Linked List has a node, which consists of one or more attributes.

Usually, a Linked List contains data (storing the value of the node) and the next (storing the address of the next node).

### String

String can be termed as an array of characters, where each character is stored in a contiguous memory location.

## Problem Statement

We are given a string s, and we have to construct a singly linked list from it. Each node of the linked list should contain at most one value of the string.

### Example 1

Given a string s, convert it into a singly linked list and return the head / starting pointer of the linked list.

Input:

``s = “coding”``

Output:

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

Note: We are supposed to return the address of the head of the linked list. In this case, we are supposed to return the address of node c.

Explanation:

The head node of the linked list should be the first character of the string, and so the head should be pointing to the first character of the string.

Then the remaining characters of the string should be connected to the head via a linked list, i.e by storing the address of the next element in their node.

So, in this case, the head should be pointing to the node containing the letter c as a value.

### Example 2

Given a string s, convert it into a singly linked list, and return the head / starting pointer of the linked list.

Input:

``s = “ninjas”``

Output:

``n -> i -> n -> j -> a -> s ``

Note: We are supposed to return the address of the head of the linked list. In this case, we are supposed to return the address of node n.

Explanation:

Here also, as explained above, the head node of the linked list should be the first character of the string, and so the head should be pointing to the first character of the string.

Then the remaining characters of the string should be connected to the head via a linked list, i.e by storing the address of the next element in their node.

So, in this case, the head should be pointing to the node containing the letter n as a value.

## 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.

### 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``

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

"""
converts a string to a linked list
"""

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

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

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

print()``````

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

// temporary variable for iterating

// 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;
}

{
cout << head->data << " -> ";
}
cout << endl;
return 0;
}``````

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

// 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;

}
}
System.out.println();
return;
}
}``````

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)

### 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?

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.