Apologies in advance for the wonky formatting.

This started as a gist at https://gist.github.com/KMSkelton/1b1c0ecf59d8b7406e3495f831184ad1

and I decided to also make it a blog post for easier reference. It

turns out gists are not easy to get to via Github on my phone.

I am using Python3 because it is better suited for data structures

than is JavaScript. I understand there may be some code formatting

issues that betray my background in JavaScript, and I am happy to

discuss best practices. The mea culpa and ado concluded…

A linked list is a collection of data comprised of nodes.
Each node is either empty or it contains "cargo" and a reference
to the next node in the list (for a singly linked list) or
references to the next node and the previous node (for a doubly
linked list). The advantage to linked lists is that we do not have
to allocate memory to them; the nodes will add themselves to
memory wherever they have room. Insertions are super fast [O(1)]
as are removals because we typically work from the ends.
The trade off is that the entire list has to be traversed to find
the data being requested, so all find operations are O(n).
There are no external references to locations in a linked list
(unlike an array which is indexed and is contiguous in memory).

This is the most basic form of a node in a linked list:
class Node:
def __init__(self, cargo=None, next=None):
self.cargo = cargo
self.next = next
def __str__(self):
return str(self.cargo)
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
This inserts three integers into three locations that are
patterned after the Node class above. It will be more useful if we
are able to retrieve more than one item that we already know the
location of (i.e. let's add links).
node1.next = node2
node2.next = node3
This is OK for brute force creation of the most basic of linked
lists. As it is we can search for a Node if we know it's there,
but we can't return a list or remove a Node.

A little functional panache will make things easier for searching
and updating the list. From the top we'll establish all the
properties of the Node:
class Node:
def __init__(self, cargo=None, next=None):
self.cargo = cargo
self.next = next
def getCargo(self):
return self.cargo
def setCargo(self, val):
self.cargo = val
def nextNode(self):
return self.next
def setNextNode(self,val):
self.next = val
#Next we need to be able to make and modify the linked list itself
#this prints as a STACK or first-in last-out (FILO) or
# Last In First Out (LIFO) implementation
def __init__(self,head=None):
self.head = head
self.size = 0
def getSize(self):
return self.size
def addNode(self, cargo): # Typically stacks call this a push
newNode = Node(cargo, self.head)
self.head = newNode
self.size += 1
return True
def printNodes(self):
current = self.head
while current:
print(current.cargo)
current = current.nextNode()
# Alias LinkedList as myList to make things slightly easier
myList = LinkedList()
myList.addNode(4)
myList.addNode(50)
myList.addNode(37)
myList.printNodes() # 37 50 4
# Let's simply discover whether a value exists in the linked list
# (True or False). This is done by traversing through each
# node and comparing node.cargo to the value in question.
def findNode(self,value):
current = self.head
#as long as there is a 'self' this process will continue
while current:
#compare the cargo to the value
if current.getCargo() == value:
return True
current = current.nextNode()
return False
# Finally let's remove a node from the list. We'll need to keep
# track of where we are (current) and where we've been (previous)
# This removal step begins with a search, so the worst case
# scenario is this will take O(n) time.
def removeNode(self, value): #Typically this operation is called pop
previous = None
current = self.head
while current:
if current.getCargo() == value:
if previous:
previous.setNextNode(current.nextNode())
else:
self.head = current.nextNode()
return True
previous = current
current = current.nextNode()
return False

# Time to make this a more traditional linked list where each new
# node is added as a tail
# This prints as a First In First Out (FIFO) structure, also
# called a QUEUE
# Making the Node class stays the same
class Node:
def __init__(self, cargo):
self.cargo = cargo
self.next = None
# Note this is slightly different from above. No reason other than
# to demonstrate that both ways work
def getCargo(self):
return self.cargo
def setCargo(self, val):
self.cargo = val
def nextNode(self):
return self.next
def setNextNode(self,val):
self.next = val
# and now we need a tail
class LinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def getSize(self):
return self.size
# Specifically it is the adding of nodes that is different than before.
# Adding a node to the tail is called "enqueueing" while removing
# the head node is "dequeueing"
# I am maintaining the continuity in my verbiage to make these
# examples as easy to relate to each other as possible
def addNode(self, cargo):
# make sure the cargo is in the correct format as a Node
cargo = Node(cargo)
if ( self.head == None ):
self.head = cargo
else:
self.tail.next = cargo
self.tail = cargo
return True
def printNodes(self):
current = self.head
while current:
print(current.cargo)
current = current.nextNode()
# Finding and removing work the same as before:
def findNode(self,value):
current = self.head
while current:
#compare the cargo to the value
if current.getCargo() == value:
return True
current = current.nextNode()
return False
def removeNode(self, value):
previous = None
current = self.head
while current:
if current.getCargo() == value:
if previous:
previous.setNextNode(current.nextNode())
else:
self.head = current.nextNode()
return True
previous = current
current = current.nextNode()
return False

#The Doubly Linked List (DLL) adds a reference to the previous Node
class Node:
def __init__(self, cargo):
self.cargo = cargo
self.next = None
self.prev = None
def getCargo(self):
return self.cargo
def setCargo(self, val):
self.cargo = val
def nextNode(self):
return self.next
def setNextNode(self,val):
self.next = val
def prevNode(self):
return self.prev
def setPrevNode(self,val):
self.prev = val
# Now we have to consider some edge cases as well as keep track of where we are
class DoublyLinkedList:
def __init__(self):
self.head = None
self.tail = None
self.size = 0
def getSize(self):
return self.size
def addNode(self, cargo):
newNode = Node(cargo)
if (self.head == None):
self.head = self.tail = newNode
else:
newNode.prev = self.tail
newNode.next = None
self.tail.next = newNode
self.tail = newNode
self.size += 1
def removeNode(self, value):
currentNode = self.head
while currentNode is not None:
if currentNode.cargo == value:
if currentNode.prev is not None:
currentNode.prev.next = currentNode.next
currentNode.next.prev = currentNode.prev
else:
self.head = currentNode.next
currentNode.next.prev = currentNode.prev
currentNode = currentNode.next
self.size -= 1
def printNodes(self):
currentNode = self.head
while currentNode is not None:
print(" prev: {}\n cargo: {}\n next: {} ".format(
currentNode.prev.cargo if hasattr( currentNode.prev, "cargo") else None,
currentNode.cargo,
currentNode.next.cargo if hasattr( currentNode.next, "cargo") else None))
currentNode = currentNode.next
return True

And there we have it. Linked Lists can be implemented in a brutish manner, or as a stack or queue. Further, adding references to where the previous node is allows us to traverse the list (potentially) faster than if we only know where the next node is.