5.1.13 - Sketched linked lists (single, double and circular).


Notes: Students should be able to sketch diagrams illustrating: adding a data item to linked list, deleting specified data item, modifying the data held in the linked list, search for a given data item.

Linked Lists
  • Definition:
    • data structure (abstract data type)
    • group of nodes representing a sequence
    • node = data + link to the next node
    • order important
    • value can occur more than once
  • behaviour
    • add element
    • remove element
    • find element
    • list end: indicated through the reference being null
    • list start: external reference which is head (ref.) referencing the start of the list
  • advantages:
    • easy adding or removing of nodes without need to relocate or reorganise the list
  • disadvantages
    • requires sequential scanning



Single linked list
  • only can move to the next field
  • can: add, remove, pass node

Screen Shot 2015-04-18 at 21.20.45.png
Source: Wikipedia - Linked List


Double linked list
  • second reference link pointing to the previous node

Screen Shot 2015-04-18 at 21.20.52.png
Source: Wikipedia - Linked List


Circular linked lists
  • the last node that is should contain the reference null, references back to the first node

Screen Shot 2015-04-18 at 21.21.02.png
Source: Wikipedia - Linked List


Sketching diagrams
  • Adding a node
    • access the previous item --> change the reference to the item you would like to insert
    • change the reference of the item you would like to insert to the next node (the node that is supposed to follow)

Screen Shot 2015-04-18 at 21.33.06.png
Source: Wikipedia - Linked List

  • Removing a node
    • delete node
    • access the previous node and change the reference to the next node after the deleted one

Screen Shot 2015-04-18 at 21.35.52.png
Source: Wikipedia - Linked List

  • Modifying

Singly_linked_list_insert_after.png

  • Searching
ll-search.gif

A great reference:
http://www.cs.rmit.edu.au/online/blackboard/chapter/05/documents/contribute/chapter/03/list-operations.html

Created By: Lucie Magister
Last update: 18/04/2015

Sources: