15 Linear data structures
16 Key concepts
16.0.1 Data structures
Linear data structures are a type of data structure where the data elements are arranged in a linear order, with each element connected to its predecessor and/or successor. There are several key linear data structures, including the following:
Arrays: An array is a collection of elements that are stored in a contiguous block of memory, with each element accessed using an index. Arrays are fixed in size, which means that the number of elements they can store must be known in advance.
Linked Lists: A linked list is a collection of elements where each element, called a node, contains both data and a reference to the next node in the list. Linked lists can be singly linked, where each node contains a reference to the next node, or doubly linked, where each node contains references to both the next and previous nodes.
Stacks: A stack is a data structure that stores a collection of elements and supports two main operations: push, which adds an element to the top of the stack, and pop, which removes and returns the top element from the stack. Stacks follow a Last-In-First-Out (LIFO) order, which means that the last element pushed onto the stack is the first one to be popped off.
Queues: A queue is a data structure that stores a collection of elements and supports two main operations: enqueue, which adds an element to the back of the queue, and dequeue, which removes and returns the element at the front of the queue. Queues follow a First-In-First-Out (FIFO) order, which means that the first element enqueued is the first one to be dequeued.
Deques: A deque, short for double-ended queue, is a data structure that supports operations at both ends. Elements can be added and removed from both the front and back of the deque. Deques can be thought of as a combination of stacks and queues.
These key linear data structures are fundamental building blocks for many algorithms and data processing tasks in computer science. Choosing the right data structure for a particular problem can have a significant impact on the efficiency and performance of the algorithm or program.
16.1 Dynamic memory allocation
Dynamic memory allocation is the process of allocating memory at runtime, rather than at compile-time. This allows programs to use memory as needed, without requiring the amount of memory to be known beforehand.
In the context of linear data structures, dynamic memory allocation is often used to create linked lists and other structures where the size of the structure may change during program execution. For example, a linked list may initially contain only a few nodes, but as more data is added, the list may need to grow in size.
In languages like C and C++, dynamic memory allocation is typically done using the malloc() and free() functions. malloc() is used to allocate a block of memory of a specified size, while free() is used to release the memory once it is no longer needed.
In languages like Python, Java, and C#, dynamic memory allocation is handled automatically by the language’s memory management system. These languages use garbage collection to automatically free up memory that is no longer being used by the program.
Dynamic memory allocation can be a powerful tool, but it can also introduce new problems such as memory leaks and fragmentation. It is important for developers to carefully manage dynamic memory allocation to avoid these issues and ensure efficient use of memory.
16.2 Linear data structures
Linear data structures are a type of data structure where the data elements are arranged in a linear order, with each element connected to its predecessor and/or successor. This means that the elements are arranged in a sequence, with one element following another in a linear fashion.
Some examples of linear data structures include arrays, linked lists, stacks, queues, and deques. Arrays store elements in a contiguous block of memory, with each element accessed using an index. Linked lists use nodes to store elements, with each node containing both data and a reference to the next node in the list. Stacks and queues are collections of elements that support operations for adding and removing elements in a specific order, with stacks following a Last-In-First-Out (LIFO) order and queues following a First-In-First-Out (FIFO) order. Deques are similar to queues, but they allow for elements to be added and removed from both the front and back of the collection.
Linear data structures are often used in computer science and programming because they provide a simple and efficient way to organize and access data. The choice of which linear data structure to use for a given problem depends on the specific requirements of the problem, including the type and amount of data being processed, and the operations that need to be performed on that data.
17 Learning outcomes
17.1 Describe linear data structures and its operations using pseudocode
Here’s an overview of linear data structures and their operations using pseudocode:
17.1.1 Arrays
- Initializing an array:
n = 10 # size of array
array = [0] * n # initialize array with all elements set to 0- Accessing an element:
x = array[i] # access element i in array- Updating an element:
array[i] = x # set element i in array to x17.1.2 Linked Lists
- Initializing a linked list
head = None # initialize head pointer to null- Inserting a node at the beginning:
node = Node(data) # create new node with data
node.next = head # set next pointer of new node to current head
head = node # update head pointer to new node- Deleting a node from the beginning:
if head is not None:
head = head.next # update head pointer to next node17.1.3 Stacks
- Initializing a stack:
stack = [] # initialize an empty list- Pushing an element onto the stack:
stack.append(x) # add element x to end of list- Popping an element from the stack:
x = stack.pop() # remove and return last element in list17.1.4 Queues
- Initializing a queue:
queue = [] # initialize an empty list- Enqueuing an element:
queue.append(x) # add element x to end of list- Dequeuing an element:
x = queue.pop(0) # remove and return first element in list17.1.5 Deques (double ended queues)
- Initializing a deque:
deque = [] # initialize an empty list- Adding an element to the front:
deque.insert(0, x) # insert element x at the beginning of list- Removing an element from the front:
x = deque.pop(0) # remove and return first element in list- Adding an element to the back:
deque.append(x) # add element x to end of list- Removing an element from the back:
x = deque.pop() # remove and return last element in listNote that this is just a basic overview of the operations for each linear data structure, and the actual implementation may vary depending on the specific programming language and data structure library being used.
17.2 Understand array and linked list based implementations of stacks and queues
17.2.1 Arrays for Stacks and Queues
Arrays can be used to implement both stacks and queues. In an array-based implementation, a fixed-size array is used to store the elements, and a pointer (often called “top” for stacks and “front” and “rear” for queues) is used to keep track of the current position of the element(s) in the data structure.
For a stack implemented using an array, new elements are added to the end of the array and removed from the end of the array. The “top” pointer points to the last element added to the stack, and is updated with each push or pop operation.
For a queue implemented using an array, new elements are added to the end of the array and removed from the front of the array. The “front” and “rear” pointers point to the first and last elements of the queue, respectively, and are updated with each enqueue or dequeue operation.
One limitation of array-based implementations is that the size of the array is fixed, which means that it cannot be dynamically resized if more elements need to be added than the array can hold. This can lead to inefficiencies in memory usage if the array is larger than necessary, or errors if the array is not large enough to hold all the required elements.
17.2.2 Linked Lists for Stacks and Queues
Linked lists can also be used to implement both stacks and queues. In a linked list-based implementation, a series of nodes are used to store the elements, with each node containing both the element and a pointer to the next node in the list.
For a stack implemented using a linked list, new elements are added to the beginning of the list and removed from the beginning of the list. The “top” pointer points to the first element in the list, and is updated with each push or pop operation.
For a queue implemented using a linked list, new elements are added to the end of the list and removed from the beginning of the list. The “front” pointer points to the first element in the list, and the “rear” pointer points to the last element in the list. Both pointers are updated with each enqueue or dequeue operation.
One advantage of linked list-based implementations is that they can dynamically resize to accommodate any number of elements. However, linked lists can be less efficient than array-based implementations in terms of memory usage and cache locality, since each element is stored in a separate node and requires additional memory for the pointer to the next node.
17.3 Implement a sorted linked list
Here’s an implementation of a sorted linked list in Python:
class Node:
def __init__(self, val):
self.val = val
self.next = None
class SortedLinkedList:
def __init__(self):
self.head = None
def add(self, val):
# create a new node with the given value
new_node = Node(val)
# if the list is empty, add the new node as the head
if not self.head:
self.head = new_node
return
# if the new node's value is less than the head's value,
# insert it at the beginning of the list
if val < self.head.val:
new_node.next = self.head
self.head = new_node
return
# find the appropriate place to insert the new node
curr = self.head
while curr.next and curr.next.val < val:
curr = curr.next
# insert the new node after the current node
new_node.next = curr.next
curr.next = new_node
def remove(self, val):
# if the list is empty, do nothing
if not self.head:
return
# if the value to remove is at the head, remove it
if self.head.val == val:
self.head = self.head.next
return
# find the node with the value to remove
curr = self.head
while curr.next and curr.next.val != val:
curr = curr.next
# if the value was not found, do nothing
if not curr.next:
return
# remove the node with the given value
curr.next = curr.next.next
def print_list(self):
# print the values in the list
curr = self.head
while curr:
print(curr.val, end=' ')
curr = curr.next
print()Here’s an example implementation of a sorted linked list in TypeScript:
class Node {
public value: number;
public next: Node | null;
constructor(value: number) {
this.value = value;
this.next = null;
}
}
class SortedLinkedList {
private head: Node | null;
constructor() {
this.head = null;
}
// insert a value into the linked list in sorted order
insert(value: number): void {
const newNode = new Node(value);
if (this.head === null || value < this.head.value) {
// if the linked list is empty or the new value is smaller than the head value,
// insert the new node at the beginning of the list
newNode.next = this.head;
this.head = newNode;
} else {
// otherwise, find the appropriate position to insert the new node
let current = this.head;
while (current.next !== null && current.next.value < value) {
current = current.next;
}
newNode.next = current.next;
current.next = newNode;
}
}
// print the values in the linked list
print(): void {
let current = this.head;
while (current !== null) {
console.log(current.value);
current = current.next;
}
}
}
// example usage
const sortedList = new SortedLinkedList();
sortedList.insert(3);
sortedList.insert(1);
sortedList.insert(4);
sortedList.insert(2);
sortedList.print(); // output: 1 2 3 4Here is an implementation of a sorted linked list in C:
#include <stdio.h>
#include <stdlib.h>
// Define the structure for the linked list node
typedef struct node {
int data;
struct node* next;
} Node;
// Function to create a new node
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to insert a new node into the sorted linked list
void insertNode(Node** head, int data) {
Node* current;
Node* newNode = createNode(data);
// If the list is empty or the new node is smaller than the head node, insert at the beginning
if (*head == NULL || (*head)->data >= data) {
newNode->next = *head;
*head = newNode;
}
// Otherwise, iterate through the list to find the correct position to insert the new node
else {
current = *head;
while (current->next != NULL && current->next->data < data) {
current = current->next;
}
newNode->next = current->next;
current->next = newNode;
}
}
// Function to print the linked list
void printList(Node* head) {
Node* current = head;
while (current != NULL) {
printf("%d ", current->data);
current = current->next;
}
printf("\n");
}
// Main function to test the sorted linked list implementation
int main() {
Node* head = NULL;
// Insert elements into the sorted linked list
insertNode(&head, 5);
insertNode(&head, 2);
insertNode(&head, 8);
insertNode(&head, 1);
insertNode(&head, 10);
// Print the sorted linked list
printList(head);
return 0;
}