Advanced Data Structures

Dr Ian Cornelius

Hello

Hello (1)

Learning Outcomes

Understand the concept of trees and linked-lists and their function as a data structure
Practice and implement the use of trees and linked-lists in work undertaken for lab activities

Trees

Trees (1)

What are Trees?

Trees are a connected, undirected graph with no cycles (more on this later)
Root of a tree is the topmost node, or the start node for traversal
- if a tree has a root node, it is called a rooted tree
Branches of a tree is the path from the root to an end-point; the end-point is known as a leaf
Height of a tree is equal to the number of edges
- that is those that connect the root node to the leaf node that is the furthest away
The number of edges (\(E\)) of a tree is equal to the number of nodes (\(N\)) minus one
- \(E = N - 1\)

The first advanced data structure we shall look at is trees, and these are not those things that you would typically find outdoors in parks, gardens or alongside a road. In fact, in Python, Trees are a non-linear and hierarchical data structure. They are a type of graph, and you will be introduced to the concept of graphs in another lecture. However, for now, consider a tree to be an undirected, connected graph that consists of no cycles, and I promise this makes more sense later.

There are a few terms that you will need to become accustomed to when we talk about trees. These are: “nodes”, “root”, “branches”, “leaf” and “height”. On the right-hand-side of the screen, you can see an example of a tree and how it would look in a visual form. This tree consists of multiple nodes, a couple of examples are highlighted in blue.

The root of a tree is considered to be the top-most node, therefore, considering our tree on the right, this would be the node highlighted in yellow, and this may sometimes be referred to as a “start” node. When a tree consists of a root node, it is often referred to as a rooted tree.

The branches of a tree is a path that gets you from the root node to an end-point. These end-points are often referred to as a leaf. Therefore, looking back at our tree, we can see that from node one to node five, we pass through node two to get to our leaf, which is our node five (highlighted in red).

The height of a tree is equal to the number of edges that exist in the tree. An edge is considered to be a connection between two nodes, in this instance it is the line between node one and node two. In this instance, the number of edges between node one and node eight is two branches. Therefore, the height of our tree would be considered to be two. We can also calculate the number of edges that exist in our tree by taking the total number of nodes and subtracting one from our total. In our tree example, we have ten nodes, therefore, we have a total of nine edges. We can look at this together, and count each of the individual black lines that exist in our tree.

Tress (2)

Types of Trees

There are various different types of trees:
1. Balanced and Unbalanced Trees
2. Rooted Trees
3. Binary Search Trees

Trees (3)

Balanced and Unbalanced Trees

Trees can be either balanced or unbalanced:
- for a balanced tree, every leaf is around the same distance away from the root as any other leaf
- for an unbalanced tree, one or more leaves are much further away from the root than any other leaf
A balanced tree does not need to have the same number of nodes in the left and right subtrees
- each branch (from root to leaf) must have the same height

One particular type of tree is that they can either be balanced or unbalanced. Now whether you classify this as one type or two is entirely upon you; however, I see it as one.

A balanced tree will be where every leaf is approximately the same distance away from the root node as of any other leaf that exists inside our tree. In this instance, the tree on a couple of slides previous would be considered as a balanced tree. An unbalanced tree, on the other hand, will have one or more leaves that are further away from the root node compared to any other leaf in the tree. The example on this slide is considered to be an unbalanced tree, as the path from node one to node eleven consists of three branches, opposed to the rest of the paths which only have two branches.

It is important to know that a balanced tree does not necessarily need to have the same number of nodes on the left or right-hand-side of the tree. As long as each branch from the root node to the leaf is the same height, then it will be considered to be a balanced tree.

Trees (4)

Rooted Trees

Rooted trees are trees with one node that has been designated as the root
The root node is commonly situated at the start (above all the other nodes)
- branches descend to the leaf nodes
Nodes are connected in a parent-child relationship
A parent node is a node that comes directly before another adjacent node
- the adjacent node is considered to be its child
Nodes can have any number of children
A leaf is a node that does not consist of any children

As you may have guessed, a rooted tree is a tree that consists of a single node that has been designated as the root of the tree. This node is commonly situated at the start of the tree and above all the other nodes. Branches will descend from this node to leaf nodes at the end.

Nodes in this type of tree are often connected to one another in what is known as a ‘parent-child’ relationship. The parent node of a tree is a node that comes directly before another adjacent node, where this adjacent node is considered to be the child. In the tree on the right-hand-sie we can see that the parent node twenty has two children, nodes seven and fifteen, respectively. This leads me onto the fact that a parent may have any number of children associated with it.

A node can only be classified as a leaf when that node has no children of its own. In this instance, nodes: seven, nine, and fifteen are all considered to be the leaves of this tree.

Trees (5)

Binary Search Trees (BST)

A binary tree is a tree that is rooted and every node has at most two children
A binary search tree is a special implementation of a rooted binary tree
- ordered on a way to optimise searching
Nodes of this tree type are ordered ascending (low to high):
- the nodes on the left subtree have values that are lower than the root
- the nodes on the right subtree have values that are higher than the root

Binary search trees are a special type of rooted tree that only consists of two children at most. As the ‘search’ word would suggest in its name, it is optimised in a way to facilitate searching. The nodes of this tree are ordered to be in ascending order.

They would typically be structured in a fashion whereby nodes on the left subtree will consist of values that are smaller than the root/parent node. Whereas nodes on the right subtree will have values that are larger than the root or parent node. Let’s have a look at our example tree on the right-hand-side of the screen. This tree is laid out slightly different compared to our previous examples, as this one consists of nodes with letters, and not numbers.

The root of our tree is the letter F and we can see that it consists of two children, B and G. We can see that these two nodes have been sorted accordingly. As B comes before F in the alphabet, it is placed on the left-hand-side, whilst G comes after F, and as-such it has been placed on the right-hand-side.

Let’s look at our left subtree in a little more detail. Here ee have our parent node B, and we can see that it has two children: A and D. The letter A is placed on the left-hand-side of node B as it comes before it. However, D comes to the right of B. However, why is it not on the right hand-side of F. Well, you should know your alphabet hopefully and know that technically, D comes before F, but comes after B and as such is placed on the left-hand-side of F but on the right-hand-side of B.

Now let’s move on and look at our parent node D and we can see that it has two children (or leaves in this instance), that are C and E, respectively. The leaf C has been placed on the left-hand-side of the tree as it comes before D in the alphabet. Finally, our leaf E is placed on the right hand-side, as it comes before F in the alphabet, but after D.

The same principle can be applied to numeric values, or even words. For example, if we had the words: “aardvark”, “zebra”, and “elephant”, which of these would be root node? Well, in this case, it would be “zebra” as the root node, followed by “aardvark” on the left-hand-side, and “elephant” on the right-hand-side.

Trees (6)

Methodology of a BST

Click Start to proceed!

Let’s have a look at how a binary search tree can be traversed. In this instance, we need to pick our target node, and for this tree we shall attempt to traverse to our target node, five. This has been highlighted in red on the screen.

Click Start

The first step in our methodology is to begin at the root node of the tree. In this instance, our root node consists of the value eight. We take the value of this node, and we compare it against the value of our target. We can perform a conditional check, and determine whether five is less than or equal to eight, and in this instance it will evaluate to True. As this check has evaluated to True, we move to the left-hand-side of our subtree, as we know from earlier that a binary search tree is structured in a particular instance where nodes of a lower value are always placed on the left-hand-side.

Click Next

The next step is to compare our current nodes value against our target value. In this instance, as we have moved over to the left subtree, our next node is three. We can perform the same conditional check as last time and check whether five is less than or equal to three. In this instance, our conditional check will evaluate to False, and therefore we move onto the right subtree. Once again, you should remember from earlier that we have moved to the right subtree as this is where larger values are placed.

Click Next

We have now moved onto step three, and once we repeat the process. In this instance, our current node is six, and we perform that conditional check once again, is five less than or equal to six? In this case, our check would evaluate to True, as five is less than six, and therefore we move onto the left subtree.

Click Next

We are almost at the end, and we progress on to step four. As usual, we compare our current nodes value (which is five) to that of our target value (which is also five). At this point, we have a match, where our target value and current node are both five. Hurrah! We have reached the end of our search, and it is at this point the algorithm will stop traversing the tree as we have found our value.

Click Next

There are some things that we can take away from this algorithm walk-through. The first one is that we are always traversing either to the left or right-hand-side of the tree. In this instance, the values on the one side of the tree always go unchecked. For example, if we move to the left, we discard (or forget about) the elements on the right-hand-side as they are not important to us. This approach is very similar to how the binary search algorithm is performed. However, an important aspect of this is to ensure that the binary search tree is balanced. If you cannot remember how binary search works, you may want to revisit the lecture from earlier on in this module.

Finally, the height of the tree will always determine the maximum number of comparisons that are being made. In this instance, we can see that the height of our tree is three. As there is a maximum number of three edges from the root node to leaf node five, then the number of checks that will be performed is four, the height of our tree, plus one.

Trees (7)

Efficiency of a BST

Time complexity is dependent upon the balance of the tree
A balanced tree in its:
- best case will have a time complexity of \(O(1)\)
- worst case will be \(O(log n)\), where \(n\) is the number of nodes in the tree
An unbalanced tree in its:
- best case will have a time complexity of \(O(1)\)
- worst case will be \(O(n)\), where \(n\) is the number of nodes in the tree

The time complexity and efficiency of a tree is dependent on whether it is balanced or not. For example, when a tree is balanced, then the best case for time complexity will be O(1), meaning that we can find the element on its first instance. Whereas, the worse case scenario would be O(log n), where n would be the number of nodes that exist in the tree.

For an unbalanced tree, the best case complexity is the same as a balanced tree O(1). However, the worst-case scenario is different in this instance, with it being O(n), where once again n represents the number of nodes that are in the tree.

Trees (8)

Traversing a BST

Processing the data of a tree often requires traversing
- traversing is concerned with systematically visiting every node
A tree can be traversed left to right, or right to left; depending on the application
Traversing in a particular order will specify a point in the traversal at which the node contents are processed
- processed in this instance is where we print the value of the nodes
When a node content has been processed, it is classified as visited
- each node can be visited several times during traversal
- it is only on one of the visits the nodes contents are processed
There are three common algorithms for tree traversal:
1. Pre-order
2. Post-order
3. In-order

We have discussed a binary search tree in-depth and how we could go about traversing these kinds of trees to find a particular value. For the rest of this lecture, we shall be looking at the different types of traversal that can happen.

As you will be aware, when it comes to processing the data of a tree, we are required to traverse it. When we use the term traversing, we are concerned with systematically visiting every node in the tree. You will be aware that a tree can be traversed left to right, or right to left depending upon the application of it.

When you traverse in a particular order, we will often specify a point in the traversal when the nodes’ contents are processed. When we use the term processed, we are concerned with printing the data in the node, and when each node’s content has been processed, we can classify that node as being visited. Each node in our tree can be traversed several times; however, its content will only be processed once. There are three common algorithms that are used when it comes to tree traversal, in this lecture we shall discuss each one, and walk-through an example of how it works. These algorithms are: pre-, post- and in-order traversal.

Trees (9)

Traversing a BST: Pre-Order

Click Start to proceed!

The first algorithm we shall be looking at is pre-order. Each node in this algorithm is visited before the algorithm traverses, or moves, to another node in either of the subtrees. This will make more sense shortly, I promise.

A simple recursive algorithm for this type of traversal is the following:

we visit the node
we do a pre-order traversal of the nodes to the left of the tree
we then do a pre-order traversal to the nodes to the right of the tree

Let’s go into this in a little more detail. For this walk-through, we shall consider the diagram on the right-hand-side of the screen.

Click Start

As usual, we start at our root node, which in this case would be node eight, highlighted in blue. We check whether we are able to access the left outside edge of the node itself. This means whether we can access the node before we move to another node, therefore, in this case we can, and we mark the node as visited. You can see on the screen that we have populated our visited list with node eight.

Click Next

We then move onto the next node in the list, and as you can see, we moved to the left-hand-side of our tree. Our next node in this instance is node three. Once again, we perform a check on whether we can access the node on the left outside edge, and as this can be achieved, we add our node to the visited list.

Click Next

We continue moving left on our tree, and we reach node one. Again, we check whether we can access the node on the left outside edge, and as we can we add our node to the visited list.

Click Next

From node three, we visit our next child node, node six. Once again, we perform the same old check and determine whether we can access the node on the outside edge. As this check evaluates to True we add our node to the visited list.

Click Next

We continue moving left to our parent node, and visit the next node, which is node five. I think you get the gist of the algorithm by now… we perform our check on whether we can access the node on the left outside edge, and as this evaluates to True we add the node to our visited list.

Click Next

As the previous node was considered a leaf, as it contained no children, we move back to our previous parent node, and begin moving to the right-hand-side.

Click Next

In this case, our next child is node seven. It can be observed from the diagram that we are able to access the left outside edge, and therefore we mark this node as visited.

Click Next

As this was the final node for the left-hand side of the tree, we can begin walking back to our root node.

Click Next

We are now back at our root node, and we now begin exploring the right-hand-side of our tree.

Click Next

We visit child node ten, and we perform our check: can we access the left outside edge of the node? This check will evaluate to True and as-such we add the node to our visited list.

Click Next

We move to the left of our node, and visit the child node eighteen. We can see from the diagram on the screen that we can access the left outside edge, and therefore we add our node to the visited list.

Click Next

We are almost coming to the end of this walkthrough, and we visit our next node, node twelve. Once again, we perform our check on whether we can access the node on the left outside edge. In this case, the check will evaluate to True and we can add our node to the visited list.

Click Next

Now that we have visited the leaf node of our subtree on the left-hand-side, we begin moving back to our parent node.

Click Next

We move back to our parent node, node eighteen, and we check whether we can traverse to the right-hand-side. In this case, there is no subtree on the right, and as such, we move backwards to our previous parent node.

Click Next

We have now come back to our parent node, node ten. Once again, we check whether we can traverse to the right, and in this case it would return False. Therefore, we can move back to our root node.

Click Next

Now that we are back at the root node, we can see that all our nodes have been visited. This can be seen from the diagram, whereby all our nodes have been changed to yellow, or from our list of visited nodes. Therefore, at this stage our algorithm will terminate.

Click Next

We have successfully traversed our tree in a pre-order fashion, which resulted in the nodes being visited in the following order: 8, 3, 1, 6, 5, 7, 10, 18 and 12. Some key concepts to take away from this algorithm are that a node is always classified as visited when the left-most side of the node can be reached. As such, you will always traverse around the outside of a node. This means that you will always double back-upon yourself when you reach a leaf in the tree.

Trees (10)

Traversing a BST: Post-Order

Click Start to proceed!

The next algorithm we shall be looking at is post-order traversal. WIth this type of traversing, each node is visited after the algorithm traverses both of the subtrees.

A simple recursive algorithm for this type of traversal is the following:

do a post-order traversal of the nodes on the left subtree
we do a post-order traversal of the nodes to the right of the subtree
we then visit the node

Let’s go into this in a little more detail. For this walk-through, we shall consider the diagram on the right-hand-side of the screen.

Click Start

As usual, we start at our root node, which in this case would be node eight, highlighted in blue. We check whether we are able to access the right outside edge of the node itself. This means whether we can access the node before we move to another node, therefore, in this case we cannot, and we therefore move onto our next node.

Click Next

We then move onto the next node in the list, and as you can see, we have moved to the left-hand-side of our tree. Our next node in this instance is node three. Once again, we perform a check on whether we can access the node on the right outside edge, and as per our previous node, we are unable to do so. As such, we move onto the next node in our list.

Click Next

We continue moving left on our tree, and we reach node one. Again, we check whether we can access the node on the right outside edge, and as we can we add our node to the visited list.

Click Next

We now move onto our next node. In this case, our previous node was a leaf with no further children associated with it. As such, we move back to our previous parent node, which is node three. As node three is not in our visited list, we perform a check to determine whether we can visit the right outside edge of the node, and in this case it evaluates to False. Therefore, we move onto visiting the children of this node on the right-hand subtree.

Click Next

From node three, we visit our next child node, node six. Once again, we perform the same old check and determine whether we can access the node on the right outside edge. As this check evaluates to False we move onto the next node in our list.

Click Next

We continue moving left to our parent node, and visit the next node, which is node five. I think you get the gist of the algorithm by now… we perform our check on whether we can access the node on the right outside edge, and as this evaluates to True we add the node to our visited list.

Click Next

As the previous node was considered a leaf, as it contained no children, we moved back to our previous parent node, and we repeat our check as node six is not in our visited list. As we are unable to access the right outside edge of the node, we proceed once again to move to the right-hand-side subtree.

Click Next

In this case, our next child is node seven. It can be observed from the diagram that we are able to access the right outside edge, and therefore we mark this node as visited.

Click Next

As the previous node was a leaf, we moved back to our previous parent node, node six. Here, we can perform our check once again to determine whether we can access the right outside edge, and at this point, the check evaluates to True and we can add node six to our visited list.

Click Next

We then move back to our previous parent node, node three, and we perform our check once again. Are we able to access the right outside edge? In this case, the check evaluates to True once again, and we can add node three to our list of visited nodes.

Click Next

We are now back at our root node, and as this node is not within our visited list, we perform a check and whether we can access the right outside edge. In this case, we are not able to do so, and we begin exploring the right-hand-side of our tree.

Click Next

We visit child node ten, and we perform our check: can we access the right outside edge of the node? This check will evaluate to False and as-such we move onto the next node in our list.

Click Next

We move to the left of our node, and visit the child node eighteen. We can see from the diagram on the screen that we cannot access the right outside edge, and therefore we move onto the next node in our list.

Click Next

We are almost coming to the end of this walkthrough, and we visit our next node, node twelve. Once again, we perform our check on whether we can access the node on the right outside edge. In this case, the check will evaluate to True and we can add our node to the visited list.

Click Next

Now that we have visited the leaf node of our subtree on the left-hand-side, we begin moving back to our parent node. We arrive back at node eighteen, and we perform our check, as we have not visited this node on the right outside edge. In this instance, we can now access the right outside edge, and therefore, we can add our node to the list.

Click Next

We move back, once more, to our parent node, node eighteen, and we check whether we can access the right outside edge of the node. This time, our check evaluates to True and as such we can add node ten to our list of visited nodes.

Click Next

Now that we are back at the root node, we can see in our list that node eight has not been visited. Therefore, we need to perform our check and determine whether we can access the right outside edge of the node. In this case, our check will evaluate to True and we can add our node to the visited list.

Click Next

We have successfully traversed our tree in a post-order fashion, which resulted in the nodes being visited in the following order: 1, 5, 7, 6, 3, 12, 18, 10 and 8. As you can see this time, the nodes have been visited in a different order compared to our pre-order traversal algorithm.

Some key concepts to take away from this algorithm are that a node is always classified as visited when the right-most side of the node can be reached. As such, you will always traverse around the outside of a node. This means that you will always double back-upon yourself when you reach a leaf in the tree.

Trees (11)

Traversing a BST: In-Order

Click Start to proceed!

The final algorithm we shall be looking at is in-order traversal. With this algorithm, we visit each node between each of its subtrees.

A simple recursive algorithm for this type of traversal is the following:

do an in-order traversal of the nodes on the left of the subtree
visit the node
do an in-order traversal of the nodes to the right of the subtree

Let’s go into this in a little more detail. For this walk-through, we shall consider the diagram on the right-hand-side of the screen.

Click Start

As usual, we start at our root node, node eight. At this node, we perform a check on whether we can access the bottom outside edge, and in this case our check would evaluate to False and as-such, we move onto the next node.

Click Next

We arrive at our child node, node three. Once again, the same check as before is performed, and we check whether the node can be accessed on the bottom outside edge. In this instance, this check would evaluate to False and as such we move onto our next node.

Click Next

As per the norm with our trees, we always move to the left-hand subtree first. Therefore, we arrive at our next child node, node one. As you can see from the diagram on the screen, this node is a leaf, and therefore when we apply our check on the node, it will evaluate to True. Therefore, we can populate this node into our list of visited nodes.

Click Next

As the previous node was a leaf, we now move back to our parent node, node three. We perform that same check again, and this time we are able to access the bottom outside edge. Therefore, we can add our node to the list.

Click Next

As we have traversed the children on the left subtree, we can now move onto the right subtree. Therefore, our next node to check is node six. We perform our check, and at this point it evaluates to False. We, therefore, move onto the next node in our list.

Click Next

The next node in our list is node five. Here we perform the same check once again and check whether we can access the bottom outside edge. In this case, our check will evaluate to True and we can now add the node to our list.

Click Next

As node five was a leaf, we moved back to our parent node, node six. Again, we perform a check and determine whether we can reach the bottom outside edge of the node. In this case, we can now access the edge, and we can add the node to our list.

Click Next

We move to the next node in our list, and this is node seven; also a leaf node in our tree. As we can reach the bottom outside edge of this node, we can add it to the list of visited nodes.

Click Next

We then begin moving back through the parent nodes of our tree. As node six has already been visited and exists in our list, we can move back to the previous parent node.

Click Next

Node three also exists in our list of visited nodes, and therefore we can move back once more to our root node.

Click Next

We are now back at our root node, and it can be seen from our list that we are yet to visit this node. Therefore, we perform our check to determine whether we can access the bottom outside edge. In this case, our check will evaluate to True and we can add this node to our list.

With the left-hand side of the tree visited, we can proceed with exploring the right-hand-side of our tree.

Click Next

We reach node ten, and we perform the same check. In this instance, we are unable to access the bottom of the node, and we move onto the next node in the tree.

Click Next

This time, we have reached node eighteen, and we perform the same check as last time. As per the previous node, we are unable to access the bottom outside edge, and as such, we move onto the next node in our tree.

Click Next

We reach our leaf node, node twelve. As per usual with our leaf nodes, we can access the bottom outside edge, and as such we can add this node to our list.

Click Next

We now begin to travel back to our parent nodes, and we arrive back at node eighteen. Here, we are able to access the bottom outside edge of the node, and as such, we can add it to our visited list.

Click Next

We travel back once more, and arrive at node ten. At this point, we can access the bottom outside edge of our node, and we add this node to our list.

Click Next

Finally, we have arrived back at our root node, node eight. As this node already exists in our list, there is nothing for us to do. At this point, our algorithm will terminate as we have traversed all nodes in our tree.

Click Next

We have successfully traversed our tree in an in-order fashion, which resulted in the nodes being visited in the following order: 1, 3, 5, 6, 7, 8, 12, 18 and 10. As you can see this time, the nodes have been visited in a different order compared to our pre- and post-order traversal algorithm.

Some key concepts to take away from this algorithm are that a node is always classified as visited when the bottom side of the node can be reached. As such, you will always traverse around the outside of a node. This means that you will always double back-upon yourself when you reach a leaf in the tree.

Linked Lists

Linked Lists (1)

What are Linked Lists?

Linked Lists are an ordered collection of objects
- they are referred to as a linear data structure
They differ from lists in the manner of how they store elements in the memory
A normal list in Python will use a contiguous memory block
- this will store the data element itself, and solely the data element
Linked Lists store references to the next node
- as well as the data element itself
- note, reference refers to a memory address in this instance
Variety type of linked lists, such as:
- singly
- doubly
- circular

A linked list is an ordered collection of objects and are often referred to as a linear data structure. They can be used to sequentially arrange elements of a particular data type together. They differ from the lists in Python by the manner of how they store their elements in the memory.

A typical list in Python will use a contiguous memory block to store the data element directly. However, with a linked list it contains a set of nodes that will hold the data element itself, and a reference to the next node that exists in the list.

There are different types of linked lists. We have singly linked lists, which only refer to the next node in the list. There are also doubly linked lists which provide a reference to not only the next node in the list, but the previous node too. Finally, a circular linked list is a little more difficult. If it is a singly linked list, then the next pointer of the last item will point to the first item in the list. However, if it was a doubly linked list, then the previous pointer of the first item in the last will point to the last item as well.

For the purpose of this lecture, we shall solely focus upon singly linked lists.

Linked Lists (2)

Structure of a Linked List

Each element of a linked list is referred to as a node
Every node has two different fields:
1. data: contains the value that is stored in the node
2. next: contains the reference to the next node on the list
The first node is referred to as the head
- is used as the starting point for any iteration through the list
The last node of the list must have its next reference pointing to None
- this will determine the end of the list

Node Data

The structure of a linked list contains nodes, as we have discussed earlier. Each element in a linked list is referred to as a node, and each node will consist of two fields:

a field for data: which will contain some form of data, it could be an integer, or it could be a string, etc.
a field for the pointer, otherwise referred to as ‘next’: this will contain a memory address or reference to the next node in the linked list

The first node in our list is referred to as the head, and is used as a reference or starting point for any iteration to occur within the linked list. The last element with data in a linked list is known as the tail, and this last item will have a final pointer or next value to None. The None pointer is used to determine the end of a linked list.

Linked Lists (3)

Queues and Stacks

These differ in the process of retrieving the elements
Queues will use a first-in and first-out approach, known as FIFO
Stacks use a last-in and fist-out approach, known as LIFO

There are two methods we can use when it comes to populating a linked list and retrieving elements. We can use either one of the following, a queue or a stack.

A queue will often retrieve (or remove) elements from a linked list in a manner where the first element in will be the first element removed from the list. This is often abbreviated to FIFO, which stands for “First-In-First-Out”. A stack on the other-hand will retrieve or remove elements where the last element in the list will be the first element out of the list, often abbreviated to “LIFO”, which stands for “Last-In-First-Out”. This will make sense shortly on the next couple of slides, where we shall explore each of these concepts in more detail.

Linked Lists (4)

Queues (FIFO)

Queues consist of two references to the nodes in a list
- head: points to a node in the list which is the top/first node
- tail: points to a node in the list which is the last node
The first node inserted into the list will be the first one to be retrieved
Appending new elements to the list goes on the rear (the end)
Retrieving elements will be taken from the front of the queue

Linked Lists (5)

Queue Walkthrough

Click Start to proceed!

None

Let’s have a look at an example of how a queue works when it comes to a singly linked list.

Click Start

For the purpose of this example, we will be concerned with adding some fruit to our list. In this case, the first fruit we wish to add to our list is “Apple`. Therefore, we add our node at the beginning of the list. In this instance, the term”append” means to add an item at the end of our list.

When we add our node to the list, it is approximately located at the head and tail of the list, as it is the only element to reside in it. Therefore, as it is also at the tail-end of our list, it will point to a None object.

Click Next

We now wish to add another fruit to our list, and this time I want to add a “Banana” to our list. You should recall from the previous slide that when it comes to adding items to a queue, it is always at a first-in-first-out methodology. Therefore, we append the new node to the end of our list. In this case, our “Banana” node becomes the tail of our list and will point to the “None” reference.

The node “Apple” moves to the head of the list, and the pointer is updated to point to the “Banana” node.

Click Next

I want to add one final node to my list of fruits. Therefore, I append the fruit “Cherry” to the end of the list, which you will know is referred to as the tail. This node will point to the “None” reference.

We also need to update our “Banana” node to now point to our new node “Cherry”.

Click Next

With our list fully populated, I want to now begin removing my fruits from the list. When it comes to a queue, the nodes of a list are always removed from the head of the list. Therefore, the first node to go is our “Apple” fruit.

Click Next

Coincidentally, this was also our first item in the list, and it is now the first one out.

Click Next

I really want to remove another item from our list, so we are going to focus on the next item to remove. Remember that we always remove from the head of our list, and therefore, the next node to go would be “Banana”.

Click Next

Therefore, we say goodbye to our “Banana” node.

Click Next

We have now reached the end of working with our list, and the list still contains our node “Cherry”. Some key takeaways from this concept are that when we add an item to the list, it will always be added to the end of the list, otherwise known as the tail. Whereas, when we remove an item from the list, it will be removed from the start of the list, otherwise known as the head.

Linked Lists (6)

Stacks (LIFO)

Stacks consist of a single reference to the nodes in a list
- top: points to a node in the list which is the first node
The last node inserted into the list will be the first one to be retrieved
Appending new elements to the list goes on the top (the start)
Retrieving elements will also be taken from the front of the queue

Linked Lists (7)

Stack Walkthrough

Click Start to proceed!

None

Let’s have a look at an example of how a stack works when it comes to a singly linked list.

Click Start

Click Next

We now wish to add another fruit to our list, and this time I want to add a “Banana” to our list. You should recall from the previous slide that when it comes to adding items to a queue, it is always at a last-in-first-out methodology. Therefore, we prepend the new node to the beginning of our list. In this case, our “Banana” node becomes the head of our list and will point to the “Apple” node.

The node “Apple” moves to the tail of the list, and the pointer is updated to point to the “None” reference.

Click Next

I want to add one final node to my list of fruits. Therefore, I prepend the fruit “Cherry” to the beginning of the list, which you will know is referred to as the head or top. This node will then point towards the “Banana” node.

Click Next

Coincidentally, this was also our last item in the list, and it is now the first one out. Following the last-in-first-out rule of a stack.

Click Next

Therefore, we say goodbye to our “Banana” node.

Click Next

We have now reached the end of working with our list, and the list still contains our node “Apple”. Some key takeaways from this concept are that when we add an item to the list, it will always be added to the beginning of the list, otherwise known as the head or top. Also, when we remove an item from the list, it will be removed from the start of the list.

Linked Lists (8)

Retrieving Elements

Accessing a particular element is different for a list compared to a linked list
- lists can be performed in constant time, \(O(1)\), when knowing which element you want to access
- linked lists take longer, and is performed in \(O(n)\)
  - required to traverse the whole list to find the element
Searching for a specific element in either is dependent upon the size of the list
- therefore, the time complexity is \(O(n)\)
- you are required to iterate through the entire list to find the element

When it comes to retrieving elements from a linked list, it differs quite differently when compared to a list in Python. For instance, accessing an element in a list can be performed in constant time, dependent upon you knowing which element it is that you wish to access through its index. However, with a linked list, you need to traverse the whole list to find the element you want, and as such it will take longer to perform. There is no specific index number you will be able to access. Therefore, in this instance, it would be dependant upon the number of nodes that exist in the linked list.

When it comes to searching a list or linked list for a specific element, it also is different, and it would ultimately depend upon the size of the list and linked list. In this instance, you will also be required to iterate throughout the list to find the element in particular you were searching for.

Linked Lists (9)

Inserting Elements

Inserting elements to a list can be done using:
- prepend() - insert an element at the beginning of a list
- append() - insert an element at the end of a list
Prepending or appending elements at the beginning or end of a list is done in constant time

Depending on how you may go about implementing your linked list, there will be some functions that you would want to implement to ensure that elements can be inserted into the list. For example, you may want to implement functions for prepending an element, and it will go at the front of the linked list. Whereas a function to append an item at the end of a list would also be required, depending on whether you are using a stack or queue methodology.

When it comes to prepending or appending an item in a linked list, it is done in constant time. This is because it will be inserted either at the beginning (the head) or the end (the tail) of a linked list.

Linked Lists (10)

Removing Elements

Removing elements from a list can be done using either:
- remove() - removes an element from the beginning of a list
- pop() - removes an element from the end of a list

Linked Lists (11)

Time Complexity

Linked lists are always constant in their time complexity when it comes to inserting and deleting elements
They have a performance advantage when implementing a queue
- elements inserted and removed at the beginning of a list
However, linked lists have the same performance when implementing a stack
- elements are inserted and removed at the end of the list

Goodbye

Goodbye (1)

Questions and Support

Questions? Post them on the Community Page on Aula
Additional Support? Visit the Module Support Page
Contact Details:
- Dr Ian Cornelius, ab6459@coventry.ac.uk