Data Structures 2023 with verified questions and answers

Static The size of the data structure cannot change at runtime. It has already been allocated a fixed amount of space in memory. Dynamic Size of the data structure can expand or shrink during runtime. It can be allocated more or less space in memory as needed. Immutable Structure and data cannot be changed at runtime. Data cannot be added, edited or deleted. Mutable Structure and data can be changed at runtime. Able to edit, add or delete data Record A collection of related fields. Can be looked at like a database. Can hold different data types. Steps: 1) Create record structure 2) Define attributes and data types 3) Assign data to attributes student = record ID integer firstname string surname string age integer d.o.b date endrecord name = Ayo = 18 To access specific attributes: name // Ayo List An ordered data structure with each element accessed via an index. Can be used to implement other data structures such as queues, stack or tree. Tuple Very similar to a list. A type of list that cannot be edited. Key differences: Immutable - Elements cannot be changed or edited during runtime. Different data types - Elements can be of different data types Tuple uses normal brackets (). Elements are still accessed by index Useful in situations where the data needs to remain unchanged but still accessible by index. Linked List Very valuable data structure. It is extremely versatile. Dynamic data structure (can expand and shrink in size) that uses pointers to locate the next element in the list. The elements are not necessarily stored in contiguous locations in memory, instead a pointer in used to locate the next element in the list. Each element has a data field and and a pointer field holding the address of the next element in the list. Advantageous over arrays as they are dynamic, if no elements are in the list it will take up minimal memory. Compared to array which takes up a specified amount regardless of if it is full or not. Benefits and drawbacks of linked lists Benefits: Advantageous over arrays as they are dynamic, if no elements are in the list it will take up minimal memory. Compared to array which takes up a specified amount regardless of if it is full or not. Drawbacks: The space required to store the pointers can be more than the actual data. Imagine if using 64 bit address to only hold very little data Since the nodes are not stored contiguously, we cannot access an element directly like an array which uses its index has O(1). In linked lists, you have to begin from the start and work through following the pointers. The time taken gets longer as the size of the list increases O(n). Implementing and uses of Linked Lists Use an array along with 3 global variables: start = points to the first item in the list nextFree = holds next available free space Possible uses: - Implementing undo functionality (back in browsers) - Helping OS job queues Inserting into a Linked list Place item at location given by free pointer Identify item's position in the list. (might be linear search). If that position is the start of the list: Set item's pointer to start value Reset start value to new item's location Else: Temporarily store the previous item's pointer Set previous item's pointer to new item's location Set new item's pointer to previous item's pointer (the one we temporarily stored) endif Increment free pointer by 1 Array A finite ordered set of elements of the same data type. Ordered = Each element has an index Finite = Predefined space allocated Static data structure, once declared its size cannot change. Uses square brackets []. One-dimensional Array team ["Arsenal", "United", "Pool", "City"] Accessing: team[1] // United Update: team[2] = "Chelsea" // Arsenal, United, Chelsea, City Two-dimensional array Arrays can have two or more dimensions. Two-dimension is like an array within an array. Can be viewed as a table. Declaring: Array board [5,5] board [0,0] = "king" Stack A LIFO (Last In First Out) data structure. The last element to be entered in will be the first to be retrieved. A single pointer is used, locating the item at the top of the stack. Pop - the item at the top of the stack is removed and returned. The pointer decrements by 1 Push(item) - Item is added to the top of the stack. Pointer increments by 1 Operations: - Pop() - Push - isEmpty - isFull Graph Dynamic data structure for modelling complex relationships or connections between items. It is a set of vertexes/nodes connected together by edges. The edges may be weighted indicating a cost of going down that path. Sparse Graph: - Has roughly the same amount of edges as vertices Dense Graph: - Has many more edges compared to vertices Graphs can either be directed or directed. Possible uses of a graph: - Network connections (packet directions) - Navigation (google maps) - Social media (mutual friends) - Web pages (following links, web crawlers) Undirected graph All edges are bidirectional. It is possible to go both ways. Still has vertices and edges, there are usually no arrows. Directed graph There is a specific flow to go from node to node. Useful when modelling streets as there are likely to be one way streets. Weighted edges The edges of a graph may be weighted. This means there is a cost associated with going down a specific edge. The weight or cost depends on the context of the graph. For navigation it could be distance or time taken. Both directed and undirected graphs can be weighted. If the program is required to make a decision, the weighted graphs is a good way to implement. Representing a graph There are two ways of representing a graph. Adjacency Matrix Adjacency List Adjacency Matrix Looks like a table with the nodes as both the columns and rows. Can be implemented using a 2D array. An entry at [row, column] indicates a connection between the nodes. In an unweighted graph a value of 1 is entered. If weighted then enter the cost. Find node in row first then column. If undirected graph, we have to represent both combinations. Enter the same value. Benefits: - Excellent for storing dense graphs. Since little memory is wasted on empty cells - Convenient to work with Drawbacks: - Terrible for sparse graph as there will be numerous empty cells, wasting memory Adjacency List Each vertex maintains a list of all its neighbours. Lay out two-column table whose rows are labelled with the name of each vertex. In the second column enter all vertices which is it connected to. For weighted graphs, dictionaries can be used to implement this. Benefits: - Memory efficient, only uses storage for connections. Suitable for sparse graphs - Does not store more data than required Traversing a graph Traverse means to visit every node exactly once. Depth-first traversal: - Go all the way down one route, before backtracking and taking the next available route - Implemented using a stack Breadth-first traversal: - Moving through the graph layer by layer - Implemented using a queue Depth-first traversal The search goes as deep as it can down one path, once it reaches the end it backtracks and follows the next available unvisited path. This continues until there are no more paths to explore. Best way to implement this is with a stack. As we follow a path, each vertex we meet is pushed onto the stack. This continues till we have reached the end of the path. Backtracking involves popping the previous item off the stack one at a time. This continues until we come across a vertex which has adjacent unvisited vertices. Follow that path, pushing vertices onto the stack and popping when we reach a dead end. Eventually there will come a situation when the stack is completely empty and the whole graph has been traversed Breadth-First Traversal Start at the first vertex and visit every node connected to it. Then visit all the neighbours of the 2nd node then all the neighbours of the 3rd node. Effectively moving through the graph layer by layer. First examining the layers close to the first vertex then moving down to the layers furthest away. Tree If the data to be represented has a hierarchy to it, then a tree is most suitable as it can maintain the organisation of the data. Main uses for trees: - Manipulating hierarchical data such as folder structures - Making information easy to search - Manipulating sorted lists of data Structure of a Tree A general tree can have any number of child nodes connected to a parent node. A binary tree can only have at most two child nodes (0,1 or two child nodes) Node - contains the tree data Edge - A line that connects two nodes. Every node is connected by an edge apart from the root node Root - Highest node in a tree. Has no incoming edges Child - A node that has a related node higher up in the tree. The set of nodes with the same edges coming from a higher level node. Parent - A node that has a child node. Leaf node - A node that has no children Constructing a binary search tree Place the first item as the root node Then for each item: - Compare to current node going down the branch - If it is less than, branch left - If it is more than, branch right - Repeat for each item Searching a binary Tree Compare item with root node: - If more than, branch right - If less than, branch left Traversing a binary tree This means to visit every node in the tree once. There are different orders to this: - Pre-Order Traversal (Root, Left, Right) - In-Order Traversal (Left, Root, Right) - Post-Order Traversal (Left, Right, Root) Each order is a recursive function. Pre-Order Traversal (Depth-first traversal) Otherwise known as a depth-first search. Root node is visited first, then the left subtree and finally the right subtree. The same rule is applied again until all nodes have been visited. Recursive. Uses of Pre-Order traversal: - Make a duplicate of the tree - Produce prefix notation Rules: Root, Left, Right - Visit the root - Traverse left subtree - Traverse right subtree In-Order Traversal This retrieves the data in a sorted order. Rule: Left, Root, Right - Traverse the left subtree - Visit the root - Traverse the right subtree Post-Order Traversal Can be used to delete a tree as it removes the nodes such that no child node is left behind. Rule: Left, Right, Root - Traverse the left subtree - Traverse the right subtree - Visit the root Hash table Data is stored in a table (an array or list) by passing it through a hash function. This hash function will generate a memory address to store the data item. When the item is to be searched for again, it is passed through the hash function which will generate the same address so it can be easily found. An example hash function is the modulo one. Modulo takes the remainder of 2 numbers divided by each other. 5 MOD 11 = 1 Allows very fast and efficient searching of an item in a data set by passing it through the hash function. Problems with hash table Sometimes, 2 different items will produce the same hash value when passed through the function. It is called a collision. A collision is when two keys are hashed to the same address. This is inevitable in most hashing algorithms. The best way to deal with them is to find the next available memory address and store it there or a different method which will be stated. Uses of hash tables Primarily used for swift and efficient lookup of data. Indexes in a database would use a hash table because they need to be retrieved instantly. Password authentication and error checking are other possible uses