142-data-structures Flashcards
arrays
- an area of contiguous memory
- used to store variables (of the same type)
- a set of data items of the same type grouped together using a single identifier
- each of the data items is addressed by the variable name and a subscript
- the first element is stored at index 0
- 9369319 is stored at prime[0]
Arrays hold multiple elements of data, but all elements must be of the same data type.
An array is an ordered, finite set of elements of a single type.
A 1D array is linear and is always taken as zero-indexed unless stated otherwise.
Elements are selected using the syntax: oneDimensionalArray[x], where x is the position of the element.
Arrays are a static data structure and cannot be changed in size once set up.
Lists are different from arrays because the elements in a list are not necessarily contiguous.
Arrays support only a single data type (homogeneous), and most other languages support arrays as unique data structures.
Arrays are mutable and can be changed after they have been created.
Arrays are ordered collections of items.
random access - the ability to access a specific element directly given its index. This is possible in an array
records
A record is a row in a file that consists of fields, and is commonly used in databases.
Each field in a record can be identified using the syntax recordName.fieldName.
Records are made up of fields, which are variables that can have different data types.
A record must first be created by defining its structure and creating a variable from that structure.
The syntax for creating a variable from a record structure is: variableName : recordStructureName.
The attributes of a record can be accessed using the syntax variableName.attributeName.
Records are useful for collecting together related variables and data.
Steps for using a record data structure include defining the record structure, declaring a variable or array to use with the record structure, and assigning/retrieving data from the variable record.
list
A list is a data structure that holds multiple items of different data types.
Items in a list can occur more than once and are ordered.
Unlike arrays, items in a list can be stored non-contiguously and can be of more than one data type.
Lists are mutable, meaning they can be changed after they have been created.
Items in a list can be added, removed, or replaced, making them a flexible and dynamic data structure.
list operations
isEmpty= checks if list is empty
append()= adds a new value to end of list
remove()= removes value first time it appears in list
search= searches for value in list
length= returns length of list
index= returns position of item
insert(position, value) = insert value at a given position
pop()= returns and removes the last value in list
pop(position)- returns and removes the value in list at given position
linked list
A linked list is a dynamic data structure that holds an ordered sequence of items.
Each item is an object called a node with a data field and a pointer field to the next node.
The last node has a null pointer and the location of the first node is stored in a variable.
Linked lists are not fixed in size and can store data anywhere in memory.
The first item is called the head and the last item is called the tail.
Traversing a linked list involves following the pointers from one node to the next until the end is reached.
Linked lists provide a foundation for other structures like stacks, queues, graphs, and trees.
Doubly linked lists have an extra pointer to the previous node, and circular linked lists have the last node pointing to the first node.
What are the applications of a linked list?
Operating systems to manage process blocks in a ready state
Image viewers to switch between previous and next images
Music players to store tracks in a playlist
Web browsers to navigate backwards and forwards
Hash table collision resolution as an overflow
Maintaining a file allocation table of linked clusters on secondary storage
Operations that can be performed on a linked list:
Add: adds a node to the linked list
Delete: removes a node from the linked list
Next: moves to the next item in the list
Previous: moves to the previous item in a doubly linked list
Traverse: a linear search through the linked list
Manipulating a linked list:
Adding a node involves editing pointers and updating pointer fields
Removing a node involves updating pointer fields to bypass the deleted node
Linked lists waste memory when nodes are deleted but not removed from the list
Linked lists require more memory than arrays since they store pointers
Items in linked lists can only be traversed in sequence
Adding an item to a linked list:
Check there is free memory for a new node
Create a new node and insert data into it
If the linked list is empty, the new node becomes the first item
If the new node should be placed before the first node, the new node becomes the first node and points to the second node
If the new node is to be placed inside the linked list, traverse the list to find the correct position and update pointers
Deleting an item from a linked list:
Check if the linked list is empty
If the first item is the item to delete, set the start pointer to point to the next node
If the item to delete is inside the linked list, traverse the list to find the item and update pointers to bypass it.
linked lists algorithm
class Node
//the node class
property next
//stores the next node in the chain
property data
//stores the data for this node
end class
class LinkedList
property head
//stores the node at the start of the chain
procedure printNodes()
//iterates through all the nodes and prints them
current = head
//this structure can be used for searching for a node as well
while (current!=null)
print(current.data);
current=current.next;
end while
end procedure
procedure AddLast(data)
//adds an item to the end of the list
if (head==null)
//if there is no head node then add at the start
head=new Node()
head.data=data;
head.next=null;
else
toAdd=newNode()
toAdd.data=data;
Node current=head;
while (current.next!=null)
//iterate through the nodes until a null one is found
current=current.next
end while
current.next=toAdd
//adds the node once the end has been found
end if
end procedure
end class
//the same method can be used to iterate through the nodes to find one to delete
Data Structure Types
Static - structure size cannot change at runtime
Dynamic - structure size can change at runtime
Immutable - structure size and data cannot be changed at runtime
Mutable- structure size and data can be changed at runtime
Are tuples a dynamic or static data structure?
Tuples can be either dynamic or static depending on their implementation. A tuple with a fixed number of items and immutable data is considered a static data structure, while a tuple with variable-sized data or a mutable list is considered dynamic. For example, score=(5,0,12) is a static immutable tuple, while score = (“John”, 5, scorelist[]) is a dynamic mutable tuple that can change size and data at runtime.
tuple
A tuple is an ordered set of values of any type.
Tuples are like lists but are immutable; their elements cannot be added, removed or changed once a tuple has been created.
Tuples are initialised using regular brackets and elements are accessed in the same way as elements in an array.
Tuples are a fixed size set at the point of creation, making them an immutable data structure.
Tuples can store more than one data type and are an unordered collection of items.
Example code: animals = (‘cat’, ‘dog’)
graph algorithm
public class Program
{
public static void Main()
{
//create node list
List<string>node=new List<string>();
node.Add("A");
node.Add("B");
node.Add("C");
node.Add("D");
node.Add("E");</string></string>
//create list of edges. Each entry to the list is an instance of the Edge class
List<Edge>edges=new List<Edge>();
edges.Add(new Edge("E","A",7));
edges.Add(new Edge("E","B",4));
edges.Add(new Edge("B","C",9));
edges.Add(new Edge("C","D",2));
edges.Add(new Edge("D","B",3));</Edge></Edge>
//check if edge(B,C) exists
foreach(Edge e in edges){
if (e.start==”B” && e.end==”C”){
Console.WriteLine(“Edge exists”);
}
}
//find all nodes connected to B
foreach(Edge e in edges){
if (e.start==”B”){ //finds all the edges that start with B
Console.WriteLine(e.end);
}
if (e.end==”B”){ //finds all the edges that end with B
Console.WriteLine(e.start);
}
}
}
}
class Edge
{
public string start; //the Edge class stores the start node
public string end; //end node
public int weight; //and weight of the edge
public Edge(string s, string e,int w){ //constructor method
this.start=s;
this.end=e;
this.weight=w;
}
}
Graph
A graph is a set of vertices/nodes connected by edges/arcs.
Graphs can be directed or undirected, and weighted or unweighted.
Graphs can be implemented using an edge class that stores start node, end node, and weight of each edge.
Nodes are stored in a list and edges are stored in a separate list.
Computers can process graphs using an adjacency matrix or an adjacency list.
Graphs allow each vertex to have more than two edges and point to any vertex in the data structure.
Edge values can represent distance, time, bandwidth, or other relationships between vertices.
Edge values are required for some algorithms using graph data structures like Dijkstra’s algorithm.
Graph applications
Mapping road networks for navigation systems
Storing social network data
Resource allocation in operating systems
Representing molecular structures and geometry.
Graph implementations
Graphs can be implemented using:
- Objects or a dictionary called adjacency lists
or - An array called an adjacency matrix, where rows and columns represent vertices and edges, and 1 represents an edge between two vertices.
inked list implementations
Implementing linked lists using an array:
Uses a static array stored contiguously in memory.
Requires the use of an index register to locate items.
The items may be stored in a different order than in the linked list due to pointers.
Implementing linked lists using objects:
Any available memory address can be used to store data.
Each node points to the next in the structure, so the data does not need to be adjacent.
The memory footprint is not determined at compile time and can change dynamically at runtime.
graph operations
Adjacent: returns whether there is an edge between two vertices
Neighbours: returns all the vertices between two vertices
Add: adds a new vertex to the graph
Remove: removes a vertex from the graph
Add edge: adds a new edge connecting one vertex to another
Remove edge: removes an edge connecting two vertices
Get vertex value: returns the data stored in a vertex
Set vertex value: sets the data for a vertex
Get edge value: returns the value of an edge between two vertices
Set edge value: sets the value of an edge between two vertices
Add operations on a graph
No single algorithm for adding an item to a graph, as it depends on the graph being used and the item being added. Efficient algorithm needed to traverse the graph to find a specific node. Binary tree provides a specific algorithm for deleting an item.
Search operations that can be performed on a graph:
Depth first search: visits each vertex and explores each branch before backtracking.
Breadth first search: visits each neighbouring node before moving to the vertices at the next depth.
Traversal operations that can be performed on a graph:
Pre order traversal
In order traversal
Post order traversal
adjacency matrix
way of representing a graph where each vertex is assigned a numerical index and the presence or absence of an edge between vertices is represented in a matrix format. This matrix has rows and columns representing vertices, and a 1 or 0 in the intersection of each row and column indicating whether there is an edge between those two vertices. The adjacency matrix is convenient to work with because it provides quicker access times to check if there is an edge between two vertices. It is also easy to add new nodes to the graph, as adding a new row and column to the matrix is a simple task
adjacency list
adjacency list is a way of representing a graph where each vertex is stored as a node and each node maintains a list of its adjacent vertices. This means that each vertex has a list of all the vertices it is connected to. The adjacency list is more space efficient for large, sparse networks, where most vertices are not connected to each other. This is because it only stores information about the vertices that are actually connected, rather than creating a large matrix where most entries are 0. However, working with an adjacency list can take longer to check if two vertices are adjacent, as it requires searching through a list to find the desired vertex.
Stack
Stacks are a LIFO (last in, first out) data structure
Stacks have a top pointer that keeps track of the top element
They can be implemented as either static or dynamic structures
Stack operations include push (adding to the top), pop (removing from the top), and peek (viewing the top element without removing it)
Stacks are commonly used for reversing actions, such as going back a page in a web browser or using an “undo” button
Stacks are essential for computer operations and are often implemented using a pointer to the top element.
Stack overflow
any attempt to push an item onto a full stack
Stack underflow
any attempt to pop an item off of an empty stack
stack implementations
Stacks can be implemented using arrays or object-oriented techniques.
Stacks implemented using arrays are static data structures with a limited number of spaces to store items.
Object-oriented implementation allows stacks to grow and shrink dynamically, assuming there is enough memory.
The algorithm for pushing an item onto a stack using an object-oriented approach involves checking for stack overflow, creating a new node and inserting data into it, having the new node point to the previous node, and setting the stack pointer to point to the new node.
stack applications
Stacks are used by processors to track the flow of programs, allowing subroutine calls to be nested, and for returning to the previous value of the program counter.
Local variables are held on the stack, and values are lost when a subroutine ends.
Interrupts can be handled with a stack.
Stacks are used for performing depth first searches on graph data structures.
Stacks can keep track of user inputs for undo operations and backtracking algorithms, such as pathfinding maze solutions.
Stacks are used for evaluating mathematical expressions without brackets using a shunting yard algorithm and reverse Polish notation.
stack operations
Push - adding an item to the top of the stack
Pop- removing an item from the top of the stack
Peek- returning the value from the top of the stack without removing it
Check size - size ()
Check if empty- isEmpty()
Return top element but don’t remove- peek()
Add to stack- push(element)
Remove top element from stack and return removed element - pop()
Check if full - isFull()
