Study Guide - Linked Lists

A study guide for simple linked lists in Java.

CSC251 Study Guide

Linked Lists Exam

Index

• Linked Lists Exam
• Index
• Linked Lists vs Arrays
• Linked Lists Properties
• Linked Lists Algorithms

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

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\

previous.link);



while (prev.link != null) {\

prev = head;\

prev = prev.link;\

}\

• 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 (head.link) 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 = pointer.link;\

}\

• 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 pointer.link
• print list through traversal\

while (pointer != null) {\

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

pointer = pointer.link;\

}\

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