Skip to main content

6. Linked Lists & Simple Sorting Algorithms

20/02/23

Linked Lists​

  • A singly linked list is a concrete data structure consisting of a sequence of nodes.
  • Each node stores elements
  • In a simple linked list, all the data is accessible from the head by just walking along the list.

Doubly Linked List​

  • Provides a natural extension on a singly linked list
  • Nodes store: element, link to next node and link to previous mode
  • Deletion at the tail is now O(1), but this uses more memory

Simple Sorting Algorithms​

Bubble Sort​

  • Often are equal with respect to the desired ordering but not necessarily that they have the same contents. One example is excel spreadsheets
  • Time complexity is t((n−1)+(n−2)+...+1)t((n-1)+(n-2)+...+1). Worst case is O(n2)O(n^2)

Selection Sort​

  • Similar to bubble sort; on each scan instead of always try to move the 'greatest element so far' immediately, we just remember its location and move it at end can
  • Same number of iterations, same number of comparisons in the worst case. Fewer swaps (one for each outer loop = n-1)

Insertion Sort​

  • Keep the front of the list sorted, and we move through the back, elements we insert them into the correct place in the front
  • In the worst case, has to make n(n−1)/2n(n-1)/2 comparisons and shifts to the right. Also O(n2)O(n^2). Best case is the array is already sorted. Becomes O(n)O(n)

Adaptive Sort​

  • Complexity for when the lists are already 'nearly sorted'
  • In many applications lists might already be close to being sorted