6 Linear data structures
This module covers linear data structures, including linked lists, stacks, and queues, and their implementations using arrays and linked lists. Linked lists allow for non-contiguous memory allocation and access through memory addresses, and the main operations associated with linked lists are insert, delete, and search. Stacks allow only insertion and removal at the top and are useful for verifying balanced pairs of elements and undoing actions. Queues operate on a First-In-First-Out basis, with elements added to the back and removed from the front. Queue operations include enqueue, dequeue, peek, and isempty.
6.1 Introduction to data structures
In this lecture, the speaker discusses data structures, which are containers that organize data in a specific way. The first half of the module covered algorithms, and this half will focus on data structures. The lecture covers linear data structures such as linked lists, stacks, and queues, as well as non-linear structures such as trees, heaps, and graphs. Each structure has specific operations or functions to manipulate the data stored within it. The lecture emphasizes that data structures and algorithms are closely related and that algorithms are necessary to operate the data stored in a data structure.
6.2 Linked lists
6.2.1 Linked lists introduction
In this lecture, the speaker introduces the concept of a linked list, a linear data structure in which each element is stored in a separate memory position and is linked to the next element through a memory address. The lecture explains the difference between linked lists and arrays in terms of their memory allocation and access, with linked lists being non-contiguous and accessed through following memory addresses. The lecture walks through the process of creating a linked list, inserting elements, and linking them. The speaker uses the analogy of a treasure hunt to explain how a linked list works. The lecture concludes with a discussion of why linked lists are considered linear data structures, despite their non-linear memory representation, and previews the next lecture, which will cover the main functions associated with linked lists.
6.2.2 Linked lists insert operation
The lecture discusses the pseudocode for the insert function in a linked list. The first step is to create a new node with the corresponding data, and then link the new node to the list by making one of the nodes or the head point to the new node, and the new node must point to some node of the list or to null. The pseudocode is shown for inserting a new node at the beginning of the list and for inserting a new node into an empty list. Two other versions of the insert function are also mentioned for inserting a new element at the end of the list and for inserting a new element in an arbitrary position in the list.
6.2.3 Linked lists delete operation
In this lecture, the delete function for linked lists is discussed. To delete a node, the node before the one to be deleted is made to point to the node after it. If the node to be deleted is the first node, the head is updated to point to the next node. The pseudocode for the delete function is explained, which involves initializing pointers tmp and prev, checking if the list is empty, and then traversing the list to find and delete the node with a given value. The execution of the pseudocode is demonstrated step-by-step with an example of deleting node 2 from a list. The lecture also provides practice exercises to simulate executing the delete function for different cases.
6.2.4 Linked lists summary
In this lecture, the time complexity of the main operations associated with linked lists was discussed. The time complexity of the insert operation depends on whether the new node is inserted at the beginning, end or at an arbitrary position of the list. If it is inserted at the beginning, the time complexity is Theta 1. If it is inserted at the end, the time complexity is Theta n. If it is inserted at an arbitrary position in a sorted list, the time complexity is Theta 1 in the best case and Theta n in the worst case. The time complexity of the delete operation depends on where the number to be deleted is located in the list. If it is at the beginning, the time complexity is Theta 1, and if it is at the end or not in the list at all, the time complexity is Theta n. The search operation has the same time complexity as using a linear search in an array. The time complexity is Theta 1 in the best case and Theta n in the worst case. Two other types of linked lists, doubly linked lists and circular lists, were briefly discussed. The next lectures will cover stacks and queues.
6.3 Stacks
6.3.1 Stacks introduction
In this lecture, the second linear data structure, the stack, was introduced. A stack is a data structure that only allows insertion and removal at the top of the stack. The operations associated with the stack are push, pop, peek, and empty. Two typical uses of the stack data structure are verifying balanced pairs of elements, such as parentheses, and undoing actions in reverse chronological order. To implement a stack, an array or a linked list can be used. The linked list implementation is more flexible, while the array implementation has better performance. The lecture ended with a detailed explanation of how to implement a stack using an array.
6.3.2 Stacks implementation
In this lecture, we learned about the stack data structure, which works like a physical stack, where objects are inserted and removed from the top. A stack can be implemented using an array or a linked list. When implemented with an array, it may run out of space or have unused memory, but the push, pop, peek, and isempty operations all have a time complexity of Theta(1). When implemented with a linked list, the push, pop, peek, and isempty operations all have a time complexity of Theta(1) as well. We also learned about some common uses for stacks, such as verifying balanced pairs of elements and undoing actions in inverse chronological order. In the next lecture, we will study the implementation of the queue data structure.
6.4 Queues
6.4.1 Queues introducion
In this lecture, the queue data structure is introduced, which works in a First-In-First-Out (FIFO) manner, where elements are added to the back and removed from the front. The enqueue operation adds an element to the back of the queue, the dequeue operation removes an element from the front of the queue, the peek operation returns the value of the element at the front of the queue, and the isempty operation returns whether the queue is empty or not. An example of a typical application of the queue data structure is in server systems where processes must wait in a queue to be served. The implementation of the queue data structure using arrays or linked lists is also discussed.
6.4.2 Queues array based implementation
In this lecture, the queue data structure was introduced, which works in a FIFO manner, and the operations associated with it were explained, including enqueue, dequeue, peek, and isempty. The implementation of a queue using arrays was demonstrated, where tail and front were used as pointers to add and remove elements. The circular array implementation was introduced to avoid the problem of not being able to use the empty space in the array. The pseudocode for enqueue, dequeue, peek, and isempty were provided, and it was shown that the time complexity of all operations of a queue implemented with arrays is theta one.
6.4.3 Queues list based implementation
In this lecture, the implementation of a queue data structure using a linked list is discussed. Unlike an array implementation, a linked list implementation does not have unused allocated memory or the need to reject elements when the queue exceeds a certain size. The front and tail pointers are used to insert elements at the tail and remove elements at the front. The enqueue operation adds a new node at the tail and updates the tail pointer, while the dequeue operation removes the front node and updates the front pointer. The operation peek returns the element at the front of the queue, and the operation isempty returns a Boolean value based on whether the front and tail pointers are null. All queue operations take constant time complexity of Theta one.