Welcome to Lesson 18!


Learning Objectives
By the end of today's class, you should know...
  • What is a linked list?
  • How is a linked list different from an array?
  • What are the advantages of using a linked list instead of an array?
  • What are the advantages of using an array instead of a linked list?
  • What is a node?
  • What is an inner class?
  • How do you write the List constructor?
  • How do you insert a new value at the head and tail of the List?


Introduction to Linked Lists

Using Lists to Store Data in Computer Science

  • We are all familiar with lists.
  • We use lists all the time for things like grocery shopping, e.g.:
    • Bread
    • Kale
    • Chocolate
  • Or, keeping track of our assignments:
    • Physics exam Wednesday.
    • Do Calc homework tonight.
    • Read short story for English.
  • Previously, you probably used an array to store a list of data in your program
String[] shoppingList = new String[3];
  • You also used Java's ArrayList - a class whose purpose is to manage an array
ArrayList<String> shoppingList = new ArrayList<String>();
  • In this lesson, we will learn an alternate approach to storing lists of data -- using a linked list
        

Review: The Problems with Arrays

  • When looking to store a collection of data (e.g. phone numbers, names in a class roster, etc), your first thought might be to use an array.
  • Arrays are a fundamental language construct in Java and as such offer a good first point of comparison.
  • However, arrays are not always the best choice to store data.
  • Can you think of any problems with arrays?
  • Note: "Under the hood" of an ArrayList is an array that Java manages for you. Therefore, ArrayLists exhibit the same problems as arrays.
Problem 1: Arrays are of fixed size:
    • But, what if I don't know ahead of time how many elements I will be storing in an array?
    • The most common approach is to make the array length larger than I think I need.
String class_roster = new String[100];
    • However, this approach may not always be sufficient.
    • Consider a start up company that needs to store customer records. 
    • When the company first begins operations, will it be able to predict roughly how many customers it might acquire in the future?
    • Maybe not.
    • It might be expensive to allot more room for storage of customer data than it actually needs. However, it could be even more dangerous not to allot enough.

Illustration of an array as 10 boxes numbered 0 through 9; an index of 0 indicates the first element in the array

Arrays are of fixed size because all elements are stored next to each other in contiguous memory locations. Image Source

Problem 2: Maintaining an ordered list is "expensive" with arrays:
    • For example, let's say that I create an array to store my class roster.
    • I wait until the second week to insert each student name alphabetically into the array, thinking that I now have all the student names.
    • But, what if there is a late add?
    • What do I do about students who drop?
    • To maintain alphabetical order in either case will require me to shift array elements either up (removal) or down to create an empty space (insertion).
    • The process of shifting elements around inside of an array in order to insert or remove is "expensive" (potentially many steps to accomplish one action)
    • The below gif demonstrates insertion in a sorted array:
https://res.cloudinary.com/monkey-codes/image/upload/v1494831769/algorithms/array_insert_vjgpaz.gif

image source

1.3: The Advantages of the Linked List

  • Linked Lists offer two distinct advantages over arrays.
Advantage 1: Linked lists are sized dynamically:
    • In other words, you don't need to know ahead of time how many data points your list will store.
    • Unlike arrays which store all the data in contiguous memory locations, linked lists store each piece of data in a unique location somewhere in the computer memory.
    • Lists keep track of the location of each piece of data by storing references to the data's location in memory.
    • Therefore, unlike when using an array, there is no need to set aside a block of memory to store a list.
    • The list simply adjusts its size each time a new piece of data is added or subtracted by storing a new reference or removing an old one.
    • We will look at how this works in a moment.
https://cdn-images-1.medium.com/max/1600/1*G43FVT5xJ1n1QDKVNZUxXQ.jpeg


Advantage 2: Linked lists allow for comparative ease of insertion and deletion:
    • Because of how data is stored, elements can be inserted and deleted without shifting elements around the linked list.
    • Instead, all that is required is for the connections (references) to be updated to reflect changes in the List.

Example showing how data is stored in a list using references. Image source

1.4. The Array Advantage

  • However, linked lists do not allow for random access.
    • In other words, we cannot directly access a specific element in the list without scrolling through the list item-by-item to find the element we are looking for.
  • Therefore, whether to use a linked list or an array is dependent on the situation. Both are important tools in your programming toolbox.



Your programming toolbox should include both arrays and linked lists


Understanding Linked Lists

Example Linked List vs Array Diagrams:

  • Storing a list of names in an array:

  • Storing a list of names in a linked list:



The Linked List Data Structure

  • Linked lists are a data structure where data is chained together using a series of references.
  • These references keep the list items in order.
  • Thus, each element in the list needs to keep track of both some data and the reference to the next element in the chain.
  • To do so, lists are comprised of special objects called Nodes.
  • A Node is an object that holds both data and a reference to the next Node in the list.
  • Linked lists are simply chains of these Nodes.
A linked list with both head and tail


Image source. Representation of a linked list. Notice that each node contains data and a reference to the next node.
  • Special Nodes within the list are head (sometimes called first or front), which indicates the first node in the list, and tail (sometimes called last or end), which indicates the end of the list. There can be other naming schemes as well.
  • head is a reference that points to the memory address of the first Node in the list. head also stores a reference to the next node in the list (the second node). However, whom does tail reference?
  • tail contains a reference that points to null. Here, null indicates that there are no further elements in the list.

Group Activity:

  • Draw the lists of values provided by your instructor as a linked list, including references to the first and last nodes.


Writing Our Own List Class

  • Although Java has its own list interface and linked list class many programmers choose to write their own customized linked list class.
  • In fact, at a very minimum, every computer science student has had to write their own linked list class at least once.
  • Therefore, we are going to dedicate significant class and homework time to writing our own linked list classes both today and over the next two classes.

Linked List Summary

  • To get us started thinking about how to write our own linked list class, let's watch the following video:
  • Video: Linked Lists in 10 Minutes


Linked List Data: Defining a Node

  • A Node is not a Java type, so we will need to build our own.
  • What kind of information does a Node hold?
    • Some data
    • A reference to the next Node's location in memory

A node contains some data and a reference to the next node's memory address. Image source

  • Therefore, we need to create a Node class with these two (private) fields.

private class Node
{
    private E data; //can store object of any type
    private Node next; //reference to the next node in the linked list
}



Self-Referential Classes

  • A class like Node above is known as a self-referential class
  • This is because the class has a reference variable that is an object of that same class:
private Node next;
  • Each next field refers to the next node in the list

The Node Constructor

  • Let's also define constructor. Recall that a good constructor initializes all fields in the class.

public Node(E data){
    this.data = data;
    this.next = null;
}

The Node as an Inner Class

  • In Java, classes can have member variables and methods, but also store other classes as a member.
  • Writing a class within another is allowed in Java. The class define inside another class is called the inner class, and the class that stores the inner class is called the outer class.
  • Since a Node is an integral part of our linked list (not to be used by other classes), we will make it an inner class of List.
public class List<E> {
    private class Node {
        private E data;
        private Node next;
        
        public Node(E data) {
            this.data = data;
            this.next = null;
        }
    } //end of class Node
    //rest of list class
}

Question: What are the advantages of making Node an inner class?


Defining the List and Its Operations

  • Now, we need to determine which operations the list will perform and what fields we need inside our list class for the list to be able to carry out those operations.
  • Let's begin with the fields we need for the list.
  • The best place to begin is by picturing what a list looks like.
  • Remember that the list has references to the first and last node (called "head" and "tail") so we can keep track of where those nodes are located in memory.
linked list with a head and tail


Representation of a linked list. Notice the node references to the head and tail nodes.

  • Let's also think of the other properties of a list
  • We know that a list has a certain number of values stored in it, aka a length. 
  • Putting all these fundamental parts of a linked list together, we can add some new private fields to the list class.
public class List<E> {
    private class Node {
        private E data;
        private Node next;
        
        public Node(E data) {
            this.data = data;
            this.next = null;
        }
    } //end of class Node
   
    private int length;
    private Node head;
    private Node tail;
} //end of class List


Writing the List Constructor

  • For the default constructor, the goal is simply to initialize the fields inside the List class with a starting value - in this case default values, as the constructor takes no parameters.
  • We have 3 fields inside our List class:
    • Node first
    • Node last
    • int length
  • What are the appropriate default values for each of these fields?
       /**
     * Instantiates a new List
     * with default values
     */
    public List() {
        head = null;
        tail = null;
        length = 0;
    }
  • Alternately, we could write a one argument constructor.

    /**
     * Instantiates a new List
     * with one node
     */
    public List(E data) {
        head = tail = new Node(data);
        length = 1;
    }

Adding Data to the List

  • This quarter, we will write two different insertion methods:
    • One to insert at the head of the List
    • One to insert at the tail of the List
  • Next quarter, we will look at how to insert in the middle of the List
  • We will begin by writing the method to insert at the head of the List
  • You can visualize the insertion using this diagram:
  • Here is the signature for this method:
    /**
     * Inserts a new first element
     * @param data the data to insert at the
     * front of the list
     */
    public void insertHead(E data) {

  • The idea behind the method is that each time it is called, a new element is inserted at the front of the List (inside a node). This element becomes the new head of the List.
  • Therefore, if I were to call insertHead("A"); and then call insertHead("B"); "B" will be the data at the head of the list after those two calls.
  • We need to consider two cases here:
  1. The edge case: The List is empty
  2. The general case: The list has one or more Nodes
  • An edge case is any case that requires you to write special code (must be handled separately).
  • Why do I need to treat the empty List differently?
    • When inserting a new node into the empty List, that node becomes both head and tail.
    • When inserting a new node into an already populated List, that node becomes the head (only)
A linked list with just one node

  • The pseudocode for this method is as follows:
  1. If the list is empty, <--edge case
    1. Create a new Node 
    2. Set head and tail references to point to this Node.
  2. Otherwise: <--general case
    1. Create a new Node
    2. Set the next reference of the new Node to point to the head of the list
    3. Set the head reference to point to the new Node
  3. Increment the length of the list (this will happen in either case)
inserting at the head of the list
  • Here is the insertHead method:
    /**
     * Inserts a new element at the head
     * @param data the data to insert at the
     * head of the list
     */
    public void insertHead(E data) {
        Node N = new Node(data);
        if (length == 0) {
            head = tail = N;
        } else {
            N.next = head;
            head = N;
        }
        length++;
    }






Wrap Up
  • Answer the Practice Exam Questions for this Lesson on Canvas

~Have a Great Day!~