Data Structures: Linked List

In Software Engineering 101, the first data structure that we’re going to look at is the Linked List. As the name says, the Linked List is a list which consists of a sequence of accessible nodes. It’s both a simple and common data structure that can be used as an approach for implementations of queues, stacks, lists and associative arrays. But why would we not just use an array for this anyway? Well, to begin with Arrays are of a fixed size meaning memory must be allocated for the specified size upon initialisation. However, Linked Lists allocate memory at runtime for the amount that is required (due to it being a dynamic data structure). If we wish to add a new item at the end of our array then this can be an issue if the array is full. If so, this would mean creating a whole new array of a larger size and copying over the values. In a

read more Data Structures: Linked List

Algorithms: Insertion Sort

Welcome to the first post on Software Engineering 101, where I aim to post weekly(ish) deep-dive articles on algorithms, design patterns, data structures and more! This week we’ll be taking a look at the Insertion Sort algorithm. Insertion Sort is an algorithm used to sort a given list of items. It does so by iterating through the list and building the sorted output one item at a time. Upon each iteration, an item is taken from the list and inserted into the correct position by comparison with its neighbours. This process is repeated until we reach the last item and there are no more left to be sorted. Insertion Sort Let’s begin by taking a look at some of it’s advantages: It’s a simple algorithm to implement Performance is very high when operating with small lists Even more so when the list is already mostly sorted, as fewer iterations of the sorting logic need to take place However, the algorithm

read more Algorithms: Insertion Sort