A linked list is a linear collection of data elements, their order is not given by their physical placement in memory. Instead they are constructed in such a way that each element points to the next. It is a data structure that consists of a collection of nodes which together represents a sequence.
Linked lists can be singly or doubly linked.
Singly linked list
A singly linked list would use a node with data and only one reference (link) to the next node.
class Node:
def __init__(self, data):
self.data = data
self.next = None
Full implementation
Doubly linked list
A doubly linked list would use a node with data and two references (links) which would point to the next and previous nodes.
class Node:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
Full implementation
class Node():
def __init__(self, data=None):
self.data = data
self.next = None
self.prev = None
class LinkedList():
def __init__(self):
self.head = None
def append(self, data):
if not self.head:
self.head = Node(data)
else:
next_node = self.head
while next_node.next:
next_node = next_node.next
next_node.next = Node(data)
def push(self, data):
if not self.head:
self.head = Node(data)
else:
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def insert(self, data, index):
if not self.head and index > 0 or index < 0:
return "Index out of range."
else:
next_node = self.head
prev_node = None
curr_index = 0
while curr_index != index:
prev_node = next_node
next_node = next_node.next
curr_index += 1
new_node = Node(data)
if prev_node:
prev_node.next = new_node
new_node.next = next_node
else:
new_node.next = next_node
self.head = new_node
def pop(self):
next_node = self.head
prev_node = None
while next_node.next:
prev_node = next_node
next_node = next_node.next
prev_node.next = None
return next_node.data
def remove(self, index):
if not self.head and index > 0 or index < 0:
return "Index out of range."
else:
next_node = self.head
prev_node = None
curr_index = 0
while curr_index != index:
prev_node = next_node
next_node = next_node.next
curr_index += 1
if prev_node:
prev_node.next = next_node.next
else:
self.head = next_node.next
def reverse(self):
prev_node = None
current = self.head
while current:
next_node = current.next
current.next = prev_node
prev_node = current
current = next_node
self.head = prev_node
def search(self, data):
if not self.head:
return "Not Found"
else:
next_node = self.head
index = 0
while next_node.data != data:
next_node = next_node.next
index += 1
if not next_node:
return "Not Found"
return index
def sort(self):
current_node = self.head
next_node = None
if not self.head:
return
else:
while current_node:
next_node = current_node.next
while next_node:
if current_node.data > next_node.data:
current_node.data, next_node.data = next_node.data, current_node.data
next_node = next_node.next
current_node = current_node.next
def print_list(self):
next_node = self.head
while next_node:
print(next_node.data)
next_node = next_node.next