tacks Stack is an ordered collection of items where the addition of new items and removal of existing items takes place at the same end. The recently added item is the one that is in position to be removed first. This ordering principle is called: LIFO - Last In First Out.
The stack operations are:
Stack() creates a new stack that is empty. Requires no parameters and returns an empty stack.
push(item) adds a new item to the top of the stack. It requires the items and returns nothing.
pop() removes the top item from the stack. It requires no parameters and returns the item. The stack is modified.
peek() return the top item from the stack. Requires no parameters. The stack is not modified.
isEmpty() test to see if the stack is empty. Requires no parameters and returns a boolean value.
size() return the number of items in the stack. Requires no parameters and returns an integer.
| time t (operation) | Stack operation | Stack content | Return value |
| t | Stack() | [] | |
| isEmpty() | [] | True | |
| t+1 | push("white") | [white] | |
| t+2 | push("red") | [white, red] | |
| t+3 | push("green") | [white, red ,green] | |
| t+4 | push("blue") | [white, red, green, blue] | |
| t+5 | push("black") | [white, red, green, blue, black] | |
| peek() | [white, red, green, blue, black] | black | |
| size() | [white, red, green, blue, black] | 5 | |
| t+6 | pop() | [white, red, green, blue] | black |
| t+7 | pop() | [white, red, green] | blue |
| t+8 | pop() | [white, red] | green |
| t+9 | pop() | [white] | red |
| isEmpty() | [white] | False | |
| peek() | [white] | white | |
| size() | [white] | 1 |
The end of the array is the input and output. So, using the append() and pop() operations cost O(1).
Some common problems which are solved with Stack logic are:
ueues Queues is an ordered collection of items where the addition of new items happens at one "rear" and removal of existing items takes place at the other end "front".
The recently added item is the one that is in position to be removed last. This ordering principle is called: FIFO - First In First Out
The queue operations are:
Queue() creates a new queue that is empty. Requires no parameters and returns an empty queue.
enqueue(item) adds a new item to the rear of the queue. It requires the items and returns nothing.
dequeue() removes the front item from the queue. It requires no parameters and returns the item. The queue is modified.
isEmpty() test to see if the queue is empty. Requires no parameters and returns a boolean value.
size() return the number of items in the queue. Requires no parameters and returns an integer.
| time t (operation) | Queue operation | Queue content | Return value |
| t | Queue() | [] | |
| isEmpty() | [] | True | |
| t+1 | enqueue("white") | [white] | |
| t+2 | enqueue("red") | [red, white] | |
| t+3 | enqueue("green") | [green, red, white] | |
| t+4 | enqueue("blue") | [blue, green, red, white] | |
| t+5 | enqueue("black") | [black, blue, green, red, white] | |
| size() | [black, blue, green, red, white] | 5 | |
| t+6 | dequeue() | [black, blue, green, red] | white |
| t+7 | isEmpty() | [black, blue, green, red] | False |
The beginning of the array is set as the rear (input) and the end of the array is the front (output). So, using the insert() operation for inserting an element cost O(n), while for taking out an element the pop() operations cost O(1).
eques Deque or double ended queue is an ordered collection of items similar to the queue. But addition of new items and removal of existing items takes place at both ends "rear" and "front". Keep track of the rear and front configuration. In this case, let's assume that the rear of the deque is at position 0.
The deque operations are:
Deque() creates a new deque that is empty. Requires no parameters and returns an empty deque.
addFront(item) adds a new item to the front of the deque. It requires the items and returns nothing.
addRear(item) adds a new item to the rear of the stack. It requires the items and returns nothing.
removeFront() removes the front item from the deque. It requires no parameters and returns the item. The deque is modified.
removeRear() removes the rear item from the deque. It requires no parameters and returns the item. The deque is modified.
isEmpty() test to see if the deque is empty. Requires no parameters and returns a boolean value.
size() return the number of items in the deque. Requires no parameters and returns an integer.
| time t (operation) | Deque operation | Deque content | Return value |
| t | Deque() | [] | |
| isEmpty() | [] | True | |
| t+1 | addFront("green") | [green] | |
| t+2 | addRear("blue") | [blue, green] | |
| t+3 | addFront("red") | [blue, green, red] | |
| t+4 | addFront("white") | [blue, green, red, white] | |
| t+5 | addRear("black") | [black, blue, green, red, white] | |
| size() | [black, blue, green, red, white] | 5 | |
| t+6 | removeFront() | [black, blue, green, red] | white |
| t+7 | isEmpty() | [black, blue, green, red] | False |
| t+8 | removeRear() | [blue, green, red] | black |
| t+9 | size() | [blue, green, red] | 3 |
The front is the last element of the array and the rear is the first element of the array. So, using the rear operation cost O(n), while the front operations cost O(1).
inked Lists (unordered) List is an ordered collection of items where each item is located in a relative position with respect to the others. There is a beginning of the list (the first item) and the end of the list (the last item).
We need to maintain the relative position of the items. However, there is no requirement to maintain contiguous memory positioning. Since, we can maintain in each item the location of the next item, then the relative position of each item can be simply to follow the link from one item to the next.
Items not constrained in their placement (left). Relative positions maintained by explicit links (right).
The only specific data required is the first item with external reference as head and the last item.
Head pointing to None
class Head: def __init__(self): self.next = None
In this configuration, each item hold at least two pieces of information: the data field and the reference to the next item.
Representation of a node
class Node: def __init__(self, data, next=None): self.data = data self.next = next
The linked list can be constructed with the head and nodes.
Terminal result:
HEAD at <__main__.Head object at 0x000001402A754B88> HEAD next None <__main__.Node object at 0x000001402A73C8C8> 2 <__main__.Node object at 0x000001402A73CA08> 3 <__main__.Node object at 0x000001402A7549C8> None
# Create the head
h = Head()
print(f"HEAD at {h}")
print(f"HEAD next {h.next}")
tail = h.next
# Create nodes
node = Node(1)
node2 = Node(2)
node3 = Node(3)
# Connect head and nodes
h.next = node.data
node.next = node2.data
node2.next = node3.data
node3.next = tail
# Print Linked List
print(node)
print(node.next)
print(node2)
print(node2.next)
print(node3)
print(node3.next)
The unordered list operations are:
List() creates a new list that is empty. Requires no parameters and returns an empty list.
add(item) adds a new item to the list. It requires the items and returns nothing.
remove(item) removes the item from the list. It requires no parameters and returns the item. The list is modified. Assume the item is present in the list.
search() searches for the item in the list. Requires the item. Returns a boolean.
isEmpty() test to see if the list is empty. Requires no parameters and returns a boolean value.
length() return the number of items in the list. Requires no parameters and returns an integer.
append(item) adds a new item to the end of the list. It requires the item and returns nothong.
index(item) returns the position of the item in the list. It requires the items and returns the index. Assumes the item is in the list.
insert(pos, item) adds a new item to the list at the position pos. It requires the items and returns nothing.
pop() removes and returns the last item in the list. It requires nothing and returns an item. Assume the list has at least one item.
pop(pos) removes and returns the item in position pos. It requires the position and returns an item. Assume the item is in the list.
The code for a Linked List is:
Terminal result:
<__main__.LinkedList object at 0x000001BBB245F8C8> <__main__.Head object at 0x000001BBB245FF48> None 4->3->2->1->None
class LinkedList:
def __init__(self):
"""Create a linked list with head pointing to None"""
self.head = Node()
def insert(self, data):
"""Insert a Node at the beginning of the linked list"""
new_node = Node(data)
current = self.head
new_node.next = current.next
current.next = new_node
def printll(self):
"""Traverse the linked list and print the elements"""
current = self.head
while current.next != None:
current = current.next
print(current.data,end="->")
print("None")
ll = LinkedList()
print(ll)
print(ll.head)
ll.insert(1)
ll.insert(2)
ll.insert(3)
ll.insert(4)
print(f"The number of elements is {ll.length()}")
ll.printll()
Insert a node at the beginnig of the list.
The head pointer is changed from None to the Node. The Node points to where the head was pointing. In a list already populated the algorithm is the same.
Insert a node in an empty list (top). Insert a node in a populated list (bottom).
Traversal is the process of systematically visit each node in the list.
Traverse a list.
The length() and search() method requires to traverse all the list to count the number of items. For this purpose we use a current variable to know the current node's data and next value.
Append a node at the end of the list.
Terminal result:
The number of elements is 5 4->3->2->1->5->None
def append(self, data):
"""Append a Node at the end of the linked list"""
new_node = Node(data)
current = self.head
if current.next == None:
new_node.next = current.next
current.next = new_node
else:
while current.next != None:
current = current.next
current.next = new_node
new_node.next = None
ll.append(5)
print(f"The number of elements is {ll.length()}")
ll.printll()
In an empty list, append works the same as insert. The head pointer is changed from None to the Node. The Node points to where the head was pointing None. In a list already populated, the algorithn is required to traverse the list and change the pointer of the last element from None to the appended Node as the newly appended Node is pointing to the end of the list, to None.
Append a node in an empty list (top). Append a node in a populated list (bottom).
Counting the number of elements requires to traverse the list.
Terminal result:
The number of elements is 5 4->3->2->1->5->None
def length(self):
"""Returns the length of the linked list"""
counter = 0
current = self.head
while current.next != None:
counter += 1
current = current.next
return counter
Search for an item requires to traverse the list checking if the item is in the list.
Terminal result:
False
def search(self, item):
"""Search for an item in the linked list"""
found = False
current = self.head
while current.next != None:
current = current.next
if current.data == item:
found = True
return found
ll.search(8)
For removing items in the list we need to add a previous pointer in addition to the current. Since with only the current pointer we don't have a way to know the information on the previous visited item.
Terminal result:
The number of elements is 3 4->3->5->None
def delete(self, item):
"""Delete an item if found"""
current = self.head
while current.next != None:
previous = current
current = current.next
if current.data == item:
previous.next = current.next
ll.delete(2)
ll.delete(1)
print(f"The number of elements is {ll.length()}")
ll.printll()
The previous must first be moved one ahead to the location of the current for performing the re-linking (removal) of the nodes.
Removing and item from the middle of the list (top). Removing the first node from the list (bottom).
