Python lists implemented using an array structure, which extends arrays' functionality by providing largers sets of operations.
Fixed array size, insertion and deletion times, are some problems of Arrays, and Python lists.
Let's create a basic class containing sigle data field:
In [1]:
class ListNode:
def __init__(self, data):
self.data = data
This is will give us just the containers that we can store data into.
In [2]:
a = ListNode(11)
b = ListNode(52)
c = ListNode(18)
In [4]:
print(a)
Since we did not define a method to show the value stored, we cannot see the value. However the values we passed to each variable is stored.
Now to make it a linked list, we have to establish a connection. To achieve this we can add another data field called next into our constructor.
In [5]:
class ListNode:
def __init__(self, data):
self.data = data
self.next = None
In [6]:
# Initial creation of nodes
a = ListNode(11)
b = ListNode(52)
c = ListNode(18)
After modifying the ListNode class and creating nodes for testing we need to use next field to assign it to next node to establish a connection.
In [7]:
a.next = b
b.next = c
In [11]:
print(a.data) # Prints the first node
print(a.next.data) # Prints the b
print(a.next.next.data) # Prints the c
Connecting all the nodes together in large list of nodes is impractical with as we did in the early example. Instead we will use a temporary external reference to traverse through the list, moving the reference along as we access the individual nodes.
def traversal(head):
curNode = head
while curNode is not None:
print(curNode.data)
curNode = curNode.next
A complete list traversal requires O(n) time.
Linear search operation can be performed on a linked list, using the same principle we did with traversal.
def unorderedSearch(head, target):
curNode = head
while curNode is not None and curNode.data != target:
curNode = curNode.next
return curNode is not None
Search operation requires O(n) in the worst case
Prepending a node can be done in constant time since no traversal is required, because we simply maintain the head reference. One simple example of prepending:
newNode = ListNode(item)
newNode.next = head
head = newNode
When we add a new value here are the steps followed:
Careful of the order of the new links, because if we link the new node into the list before modifying the head reference we lose our external reference, which results losing the list itself.
Removing nodes or unlinking them will simply extract them from the linked list structure. The steps:
None
Removing the first node is a special case, because head references the node.
# Given the head reference, remove a target from a linked list.
predNode = None
curNode = head
while curNode is not None and curNode.data != target:
predNode = curNode
curNode = curNode.next
if curNode is not None:
if curNode is head:
head = curNode.next
else:
predNode.next = curNode.next
Sometimes we need extra flexibility in our linked list than having only basic container with linear order, that's why now we'll see some features.
Using a both head and tail might save us some time, when we need to append nodes to end of the linked list.
Adding Node using Tail Reference:
# Given the head and tail pointers, adds an item to a linked list.
newNode = ListNode(item)
if head is None:
head = newNode
else:
tail.next = newNode
tail = newNode
Removing Node using Tail Reference:
# Given the head and tail references, removes a target from a linked list.
predNode = None
curNode = head
while curNode is not None and curNode.data != target:
predNode = curNode
curNode = curNode.next
if curNode is not None:
if curNode is head:
head = curNode.next
else:
predNode.next = curNode.next
if curNode is tail:
tail = predNode
We can store elements in linked list as sorted.
Linear Search
Linear search in sorted linked list will be faster since we add extra condition to terminates the loop when we reach the bigger number.
def sortedSearch(head, target):
curNode = head
while curNode is not None and curNode.data < target:
if curNode.data == target:
return True
else:
curNode = node.next
return False
Inserting Nodes
Adding a node to sorted linked list a little bit more trickier, since we have to find the spot to put our Node into sorted list.
# Given the head pointer, insert a value into a sorted linked list.
@ToDo: # Review and fix the function
def insert2sorted(head):
# Find the insertion point for the new value.
predNode = None
curNode = head
while curNode is not None and value > curNode.data:
predNode = curNode
curNode = curNode.next
# Create the new node for the new value.
newNode = ListNode(value)
newNode.next = curNode
# Link the new node into the list.
if curNode is head:
head = newNode
else:
predNode.next = newNode
Traversing and Deleting
It's pretty much the same for sorted linked lists as it was in normal linked lists.
In [ ]: