Study Guide - Linked Lists

A study guide for simple linked lists in Java.

CSC251 Study Guide

Linked Lists Exam


Linked Lists vs Arrays

  • Arrays
  • can access any element directly via indexing
  • all elements grouped together
  • sitting in 1 block of memory
  • size is fixed
  • Linked Lists
  • each element sits in own block of memory (called node)
  • nodes can only be accessed in sequential order
  • appears limited
  • size varies - nodes allocated on need basis
  • list elements can be easily inserted/removed without reallocation and at any point in the list
  • no random access to data
  • no efficient form of indexing
  • Key Differences
  • underlying layout of data in memory
  • how individual elements are accessed

Linked Lists Properties

  • overview
  • a sequence of elements arranged 1 after another with each element connected to next by a link
  • one of the simplest and most common data structures
  • can be used to implement other abstract data types
  • defintion
  • data structure of group of nodes that represent a sequence
  • diagram
Single Linked List
above is a linked list with nodes that contain 2 fields - an integer value and a link to next to the next node; last node linked to terminator symbol to signify end of list/null link
  • conceptual implementation
  • each node has data and reference (link) to next node in sequence
  • allows for insertion of removal of elements from any position in sequence
  • operations for singly linked list
  • insertion
  • deletion
  • traversal - going through entire sequence until reaching last node
  • advantages
  • dynamic data structure that allocates needed memory
  • easy implementation for insertion and deletion operations
  • other data structures can be easily executed with linked lists
  • reduce access time and can expand without more memory being used
  • disadvantages
  • usually wastes memory with pointers which requires extra storage space
  • nodes must be read sequentially
  • nodes stored in an in-contiguous manner, so more difficult to access individual nodes
  • very difficult to reverse traverse

Linked Lists Algorithms

  • constructor for an integer node in a linked list\

public Int_Node (int initialData, Int_node

initialLink) {\

data = initialData; //integer value\

link = initialLink; //reference to next node in list\


  • define empty linked list\

  • pseudocode representing empty list by storing null in head reference\keeping track of front node by using an Int_Node reference variable called head
  • add new node to empty list\

  • pseudocode
  • create new node for head
  • place data in new node’s data field
  • make head refer to null which is initial head value
  • connect new node to head
  • add node to front of list\

  • pseudocode
  • create new node
  • place data (newData) in new node’s data field
  • connect new node to front of list
  • make original head refer to new head of linked list
Diagram showing how a node is inserted after an existing nodeInserting node before existing node cannot be done directly - instead you have to keep track of the previous node and insert a node after that
  • adding anywhere but front\;

while ( != null) {\

prev = head;\

prev =;\


  • pseudocode set a reference named prev (for previous) to refer to node which is just before new node’s position
  • removing node at head\

  • pseudocode directing head to node right next to it ( so that original head is removed
  • removing node anywhere
Removing node after given node - to find and remove a particular node, you still have to keep track of the previous element
  • traverse through list\

while (pointer != null) {\

pointer =;\


  • pseudocode
  • initializing pointer to reference head
  • while loop that keeps going through entire list until pointer (or head) is null\null implying that it’s reached the last node because the last node will always have a null link since there’s nothing next to the last node so no link so null link
  • pointer referenced to next node or
  • print list through traversal\

while (pointer != null) {\

System.out.print( + " ");\

pointer =;\


  • pseudocode\same as traversal algorithm but just printing out data of pointer as you go along the node sequence with

Subscribe to my newsletter Today

In my newsletter, I share personal and career learnings, advice, collaboration opportunities, and more.