Data Structures

Data Structures

Data structures are ways to organise and store data to make it more efficient to access and modify. Understanding these is fundamental to learning how computers store and access information.

  • Array: An array is a collection of items stored at contiguous memory locations. These items should be the same type, such as integers or strings.

  • Record (or struct): A record is a complex data type which allows you to combine data items of different kinds. Records are used to structure data that naturally comes together, for example, a student could be represented as a record containing a string and an integer (their name and age).

  • LinkedList: A LinkedList is made up of nodes, where each node contains a reference to the next node in the list. In addition, each node contains a unit of data. This structure allows efficient insertions and deletions.

  • Stack: A stack is a linear data structure which follows a particular order in which operations can be performed. The order may be LIFO (Last In First Out) or FILO (First In Last Out).

  • Queue: A queue follows the FIFO (First In First Out) rule - the item that goes in first is the first item out.

  • Tree: Trees are hierarchical data structures with a root value and subtrees of children, represented as a set of linked nodes.

  • Graph: A graph data structure consists of a finite (and possibly mutable) set of vertices or nodes, together with a set of unordered pairs of these nodes for an undirected graph or a set of ordered pairs for a directed graph.

Hashing and Maps

  • Hashing: Hashing is a technique or process of mapping keys, values into the hash table by using a hash function. It is done for faster access to elements. The efficiency of mapping depends on the efficiency of the hash function used.

  • Maps (or dictionary): Maps are associative containers that store elements formed by a combination of a uniquely identifying key and a mapped value. The key value is used to uniquely identify the entry in the map.

Manipulating Data Structures

  • Insertion: This refers to adding a new data item in an existing collection of data items.

  • Deletion: This is the process of removing an existing data item from a collection.

  • Traversal: Traversing means to access each data item exactly once so that it can be processed.

  • Searching: This is the process of finding the location of a data item in a collection.

  • Sorting: Sorting is the process of arranging data items in some sequence/order.