Study Guide - Linked Lists | Frances Coronel

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;\