A linked list is a linear data structure where elements, known as nodes, are stored in sequence, with each node containing a reference (or link) to the next node in the sequence. This structure allows for efficient insertions and deletions, as it doesn’t require shifting elements like an array does.
In Python, linked lists can be implemented using classes. Each node is an instance of a Node class, which contains the data and a reference to the next node. The linked list itself is managed by a LinkedList class that maintains a reference to the head (first node) of the list.
Here’s a simple implementation:
python
class Node:
def __init__(self, data):
self.data = data # Store the data
self.next = None # Reference to the next node, initially None
class LinkedList:
def __init__(self):
self.head = None # Initialize the head of the list as None
def append(self, data):
new_node = Node(data) # Create a new node with the given data
if not self.head: # If the list is empty, set the new node as the head
self.head = new_node
return
last = self.head
while last.next: # Traverse to the end of the list
last = last.next
last.next = new_node # Set the next reference of the last node to the new node
def print_list(self):
current = self.head
while current: # Traverse through the list
print(current.data) # Print the data of the current node
current = current.next # Move to the next node
In this implementation, the Node class represents each element in the list, and the LinkedList class provides methods to manipulate the list, such as appending new nodes and printing the list’s contents.
