A study guide for simple linked lists in Java.

3 minute read

Created

0 views

CSC251 Study Guide {#csc251-study-guide style=”text-align:center;”}

Linked Lists Exam {#linked-lists-exam style=”text-align:center;”}


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

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\ [code language=”java”]public Int_Node (int initialData, Int_node initialLink) {\ data = initialData; //integer value\ link = initialLink; //reference to next node in list\ }\ [/code]
  • define empty linked list\ [code language=”java”]Int_Node head = null;\ [/code]
    • 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\ [code language=”java”]head = new Int_Node(data, null);\ [/code]
    • pseudocode
      1. create new node for head
      2. place data in new node’s data field
      3. make head refer to null which is initial head value
      4. connect new node to head
  • add node to front of list\ [code language=”java”]head = new Int_Node(newData, head);\ [/code]
    • pseudocode
      1. create new node
      2. place data (newData) in new node’s data field
      3. connect new node to front of list
      4. 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\ [code language=”java”]previous.link = new Int_Node(newData, previous.link);

    while (prev.link != null) {\ prev = head;\ prev = prev.link;\ }\ [/code]

    • pseudocode
      1. set a reference named prev (for previous) to refer to node which is just before new node’s position
  • removing node at head\ [code language=”java”]head = head.link;\ [/code]
    • pseudocode
      1. 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\ [code language=”java”]Int_Node pointer = head;

    while (pointer != null) {\ pointer = pointer.link;\ }\ [/code]

    • 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\ [code language=”java”]Int_Node pointer = head;

    while (pointer != null) {\ System.out.print(pointer.data + “ “);\ pointer = pointer.link;\ }\ [/code]

    • pseudocode\

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


Tips or Tricks?

Contact me @fvcproductions

Tags

, , , , , , , , , , , , , , , , , , , , ,

Leave a comment

Read More