Study Guide - Linked Lists | Frances Coronel

A study guide for simple linked lists in Java.

CSC251 Study Guide

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

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 🔍 zoom> 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

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 🔍 zoom> 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 🔍 zoom> 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