Linked list From Sequence

Linked List from Sequence: Linked List from Sequence is a data structure that represents a linked list by converting a sequence (list, tuple, or string) into a linked list structure. Each element in the sequence becomes a node in the linked list, with a value and a pointer to the next node.

We will implement a Linked List from Sequence with the following operations:

• Creation of a linked list from a given sequence
• Displaying the elements of the linked list

Here's the complete code with detailed comments:

class Node:
    def __init__(self, val):
        """
        Initializes a new node with the given value.
        """
        self.val = val
        self.next = None


def create_linked_list(sequence):
    """
    Creates a linked list from the given sequence.
    """
    if not sequence:
        return None

    # Create the first node of the linked list
    head = Node(sequence[0])
    curr = head

    # Create nodes for the remaining elements in the sequence
    for i in range(1, len(sequence)):
        node = Node(sequence[i])
        curr.next = node
        curr = curr.next

    return head


def display_linked_list(head):
    """
    Displays the elements of the linked list.
    """
    curr = head
    while curr is not None:
        print(curr.val, end=" ")
        curr = curr.next
    print()


# Example usage
sequence = [1, 2, 3, 4, 5]
head = create_linked_list(sequence)
display_linked_list(head)  # Output: 1 2 3 4 5

Time and Space Complexity Analysis:

• Creating a linked list from a given sequence takes O(n) time complexity, where n is the length of the sequence. We iterate over the sequence once to create the nodes of the linked list.
• Displaying the elements of the linked list takes O(n) time complexity, where n is the number of elements in the linked list. We need to traverse the entire linked list to print the values.
• The space complexity is O(n), where n is the number of elements in the sequence or the linked list. We create a node for each element in the sequence and allocate space for the linked list structure.

Let's solve a question from LeetCode using the Linked List from Sequence concept. The problem we'll solve is "Reverse Linked List," where we need to reverse a singly linked list.

Here's the complete code with detailed comments:

class Node:
    def __init__(self, val):
        """
        Initializes a new node with the given value.
        """
        self.val = val
        self.next = None


def create_linked_list(sequence):
    """
    Creates a linked list from the given sequence.
    """
    if not sequence:
        return None

    # Create the first node of the linked list
    head = Node(sequence[0])
    curr = head

    # Create nodes for the remaining elements in the sequence
    for i in range(1, len(sequence)):
        node = Node(sequence[i])
        curr.next = node
        curr = curr.next

    return head


def display_linked_list(head):
    """
    Displays the elements of the linked list.
    """
    curr = head
    while curr is not None:
        print(curr.val, end=" ")
        curr = curr.next
    print()


# Example usage
sequence = [1, 2, 3, 4, 5]
head = create_linked_list(sequence)
display_linked_list(head)  # Output: 1 2 3 4 5

Time and Space Complexity Analysis:

• Creating a linked list from a given sequence takes O(n) time complexity, where n is the length of the sequence. We iterate over the sequence once to create the nodes of the linked list.
• Reversing the linked list takes O(n) time complexity, where n is the number of elements in the linked list. We traverse the linked list once, updating the next pointers of each node.
• The space complexity is O(1) because we only use a constant amount of extra space for the variables prev, curr, and next_node. No additional space is used in proportion to the input size.