Study Guide - Linked Lists

A study guide for simple linked lists in Java.

Study Guide - Linked Lists

CSC251 Study Guide ๐Ÿ”—๏ธŽ

Linked Lists Exam ๐Ÿ”—๏ธŽ

Index ๐Ÿ”—๏ธŽ

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
    1. 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 node
Inserting 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

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
    1. initializing pointer to reference head
    2. 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

    3. 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