1.4.2 Data structures

• A linked list is a data structure that stores items in a linear sequence, with each item being linked to the next item by a pointer. The nodes which contain the data do not need to be contiguous in memory, i.e. they don't need to be stored directly alongside each other in sequence
• The main benefit of a linked list is that items can be quickly inserted or removed at any point in the list without having to shuffle other items to make space or to fill up a gap, as would be necessary with an array. The downside is that there is no fast way of finding, for example, the 100th item, you have to step through from the first item 100 times.
• A graph is a data structure in which data is stored in nodes (sometimes called vertices), which can be connected to each other in a variety of ways. The connections are called edges. Graphs can be undirected or directed (some edges can be one-way), and unweighted or weighted (edges have a number indicating the cost of travelling along that edge)
• A stack is a data structure in which items can only be added to the top of the stack and only removed from the top of the stack. For this reason it is known as a Last In First Out (LIFO) data structure.
• A queue is a data structure in which items can only be added to the back end of the queue and only removed from the front end of the queue. This makes it a First In First Out (FIFO) data structure.
• A tree is a data structure which stores items in a hierarchy. The top node is known as the root. Each node can have zero or more child nodes. A node with no child nodes is known as a leaf node.
• A binary search tree is a tree in which each node has no more than two child nodes (left and right) and the position of a newly inserted data item is determined by following a rule - lower values go towards the left of the tree, higher values towards the right.
• A hash table is a data structure in which items are stored in an array, their positions being determined by running a hash function on the item's value. This allows items to be quickly looked up without having to do a potentially slow linear search. A hash collision is when two items are given the same array index. One way of dealing with collisions is to have each array element be a linked list of items for that slot.