Linked List
# linear data structure made up of nodes and refs to the next node
# lets make some node class
class Node:
def __init__(self, value, next_node = None):
# value that the node is holding
self.value = value
# ref to the next node in the chain
self.next_node = next_node
def get_value(self):
"""
Method to get the value of a node
"""
return self.value
def get_next(self):
"""
Method to get the node's "next_node"
"""
return self.next_node
def set_next(self, new_next):
"""
Method to update the node's "next_node" to the new_next
"""
self.next_node = new_next
# now lets think of how we can make nodes interact in a way that consolidates their pieces together
# lets make a LinkedList class
# think of the idea of having a head and a tail like a snake
# where the snake can grow based upon having more links in it
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
def add_to_tail(self, value):
# wrap the value in a new Node
new_node = Node(value)
# check if the linked list is empty
if self.head is None and self.tail is None:
# set the head and tail to the new node
self.head = new_node
self.tail = new_node
# otherwise the list must have at least one item in there
else:
# update the last node's "next_node" to the new node
self.tail.set_next(new_node) # (last node in chain).next_node = new_node
# update the "self.tail" to point to the new node that we just added
self.tail = new_node
def remove_tail(self):
"""
remove the last node in the chain and return its value
"""
# check for empty list
if self.head is None and self.tail is None:
# return None
return None
# check if there is only one node
if self.head == self.tail:
# store the value of the node that we are going to remove
value = self.tail.get_value()
# remove the node
# set head and the tail to None
self.head = None
self.tail = None
# return the stored value
return value
# otherwise
else:
# store the value of the node that we are going to remove
value = self.tail.get_value()
# we need to set the "self.tail" to the second to last node
# we can only do this by traversing the whole list from beginning to end
# starting from the head
current_node = self.head
# keep iterating until the node after "current_node" is the tail
while current_node.get_next() != self.tail:
# keep looping
current_node = current_node.get_next()
# at the end of the iteration set "self.tail" to the current_node
self.tail = current_node
# set the new tail's "next_node" to None
self.tail.set_next(None)
# return Value
return value
def add_to_head(self, value):
# wrap the input value in a node
new_node = Node(value)
# check if the linked list is empty
if not self.head and not self.tail:
# if the list is initially empty, set both head and tail to the new node
self.head = new_node
self.tail = new_node
# we have a non-empty list, add the new node to the head
else:
# set the new node's `next` to refer to the current head
new_node.set_next(self.head)
# set the list's head reference to the new node
self.head = new_node
def remove_head(self):
# check for empty list
if self.head is None and self.tail is None:
# return None
return None
if self.head == self.tail:
# store the value of the node that we are going to remove
value = self.head.get_value()
# remove the node
# set head and the tail to None
self.head = None
self.tail = None
# return the stored value
return value
else:
# store the old head's value
value = self.head.get_value()
# set self.head to old head's next
self.head = self.head.get_next()
# return the value
return value
n1 = Node(1)
n2 = Node(2)
n3 = Node(3)
n4 = Node(4)
n1.set_next(n2) # n1.next_node = n2
print(n1.get_value()) # => 2
print('n1',n1)
#OUTPUT:
#1
#n1 <__main__.Node object at 0x0000026367BD0280>
`Linked List
Linked lists in Python
Implementation:
Output:
Common linked list interview questions in Python
Last updated