5 Best Ways to Create a Linked List and Display Its Elements in Python

Rate this post

πŸ’‘ Problem Formulation: Linked lists are fundamental data structures in computer science. Creating a linked list in Python involves defining the node structure and linked list functionality, along with methods to add elements and display the list’s contents. For instance, given inputs of 1, 2, and 3, we’d like to create a linked list that stores these values and then print them out in the inserted order.

Method 1: Using Class Definitions

Creating a linked list via class definitions involves defining a ‘Node’ class to store data and a reference to the next node, alongside a ‘LinkedList’ class to manage the nodes. This object-oriented approach is clean and modular, allowing for easy expansion of the linked list functionality.

Here’s an example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, data):
        new_node = Node(data)
        if not self.head:
            self.head = new_node
            return
        last = self.head
        while last.next:
            last = last.next
        last.next = new_node

    def display(self):
        current = self.head
        while current:
            print(current.data, end=" ")
            current = current.next

# Example Usage:
llist = LinkedList()
llist.append(1)
llist.append(2)
llist.append(3)
llist.display()

The output of this code snippet:

1 2 3

The provided code first defines a Node class to hold the data and a pointer to the next node. The LinkedList class then provides methods to append new nodes to the end of the list and to display the list. This is a clear and scalable way to handle linked lists in Python.

Method 2: Without a Class – Using a Nested List

Nested lists can mimic linked lists with each sub-list representing a node. The first element of the sub-list is the node value and the second element is the next node (sub-list). This method lacks a formal structure but is quick for simple implementations.

Here’s an example:

def append(node, data):
    if not node:
        return [data, None]
    else:
        node[1] = append(node[1], data)
    return node

def display(node):
    while node:
        print(node[0], end=" ")
        node = node[1]

# Example Usage:
linked_list = append(None, 1)
linked_list = append(linked_list, 2)
linked_list = append(linked_list, 3)
display(linked_list)

The output of this code snippet:

1 2 3

In this snippet, a linked list is constructed using nested lists where the first element is the value and the second is the next node. Functions are provided to append elements and display the entire list. While not adhering to formal data structure standards, it’s a viable lightweight alternative.

Method 3: Using Collections.deque

The collections.deque module in Python can be used to create a double-ended queue that can function similarly to a linked list with efficient appends and pops from both ends. This method uses Python’s built-in data structures.

Here’s an example:

from collections import deque

linked_list = deque()

# Appending items
linked_list.append(1)
linked_list.append(2)
linked_list.append(3)

# Display elements
for item in linked_list:
    print(item, end=" ")

The output of this code snippet:

1 2 3

This code uses Python’s deque class from the collections module to implement a readily available doubly linked list. It showcases an efficient way to handle linked-list-like structures using Python’s standard libraries.

Method 4: Using Generators

Generators in Python are a simple way to iterate over items without needing to build and maintain the entire list in memory. They can be used to iterate through a linked list lazily, meaning elements are processed one at a time and only when needed.

Here’s an example:

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

def append(head, data):
    if not head:
        return Node(data)
    head.next = append(head.next, data)
    return head

def display_generator(node):
    while node:
        yield node.data
        node = node.next

# Example Usage:
head = None
head = append(head, 1)
head = append(head, 2)
head = append(head, 3)

for data in display_generator(head):
    print(data, end=" ")

The output of this code snippet:

1 2 3

This code defines a generator function to yield each element in the linked list, letting you iterate over the list in a memory-efficient manner. This is especially useful when dealing with very large linked lists.

Bonus One-Liner Method 5: Using the Itertools Chain

The itertools.chain function can be used to link multiple iterables together into a single iterable, providing a concise one-liner method to create a linked list-like structure.

Here’s an example:

from itertools import chain

# Assuming linked_list is a list of iterables
linked_list = list(chain([1], [2], [3]))

print(linked_list)

The output of this code snippet:

[1, 2, 3]

This code demonstrates creating a linked list by linking together multiple one-item lists using itertools.chain. It’s quick, but not truly a linked list with node references.

Summary/Discussion

  • Method 1: Class Definitions. Strong object-oriented approach; modularity and ease of maintenance. Complexity can be overkill for small cases.
  • Method 2: Nested List. Quick and simple; avoids classes altogether. Not ideal for large data or complex operations as it lacks formal linked list methods.
  • Method 3: Collections.deque. Utilizes Python’s standard library, providing performance efficiency. However, it’s not strictly a linked list, limiting custom linked list algorithms.
  • Method 4: Generators. Memory efficient; handy for large datasets. Con: Lazy evaluation might not be suitable for all scenarios.
  • Method 5: Itertools Chain. Extremely concise for small iterables. But, this doesn’t create a true linked list with node connections.