Welcome to Lesson 2!

By the end of this 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 are some of the linked list operations?


1. Introduction to Linked Lists

1.1. 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 may have 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
        

1.2. 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 pointers 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 pointer 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 (pointers) to be updated to reflect changes in the List.

Example showing how data is stored in a list using pointers. 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


2. 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:



2.1. The Linked List Data Structure

  • Linked lists are a data structure where data is chained together using a series of pointers.
  • These pointers keep the list items in order.
  • Thus, a list needs to keep track of both the data items and the pointers to the next item.
  • To do so, lists are comprised of special objects called Nodes.
  • A Node is an object that holds both data and a pointer to the next Node in the list.
  • Linked lists are simply chains of these Nodes.


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

2.3. Group Activity:

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


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

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


3.2. Like any other ADT, our Linked Lists needs to have:

  1. A collection of data ---> Stored using Nodes
  2. Operations we can perform on the data (access, manipulate and instantiate) --> Methods


3.3. 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 pointer 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 int data;
    private Node next; //pointer to the next node in the linked list
}

  • For the moment, we are going to assume that our linked list holds integer data. We will update this part when we write our second linked list of the quarter in Lab 2.
  • Let's also define constructor. Recall that a good constructor initializes all fields in the class.

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

  • Now, since a Node is an integral part of our linked list, we are going to place this class definition inside the linked list class.
  • It is going to be one of the linked list's private fields.
public class List {
    private class Node {
        private int data;
        private Node next;
        
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    } //end of class Node
    //rest of list class
}

Question: Why do we want to make the Node class private?


3.4. 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 pointers to the first and last node (called "first" and "last") so we can keep track of where those nodes are located in memory.


Representation of a linked list. Notice the node pointers to the first and last 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 {
    private class Node {
        private int data;
        private Node next;
        
        public Node(int data) {
            this.data = data;
            this.next = null;
        }
    } //end of clas Node
    
    private int length;
    private Node first;
    private Node last;
} //end of class List

3.5. Reflection:

  • What Kind of Operations Will We Need for the Linked List?
  • Accessor methods?
  • Mutator methods?
  • Constructors?
  • Additional operations?


3.6. Lab 1 List Operations:

Constructors:

constructor: constructs a new linked list object.

Mutator Methods:


addFirst: inserts an element at the beginning of the linked list
addLast: inserts an element at the end of the list
removeFirst: removes the element at the beginning of the list   
removeLast:
removes the element at the end of the list


Accessor Methods:

getFirst: returns the first element
getLast:
returns the last element

isEmpty: tests whether the linked list is empty
getLength: returns the current length of the list

Additional Operations

toString: defines how the List will be displayed to the screen <-- Always one of the first methods to write!


3.7. Preconditions and Postconditions

  • Preconditions and post-conditions are specifications or requirements for the ADT operations.
  • Preconditions specify under what conditions an operation may be executed.


Reflection:

  • What do you think the precondition will be for the following List method:
     
/**
* Returns the value stored in the first node
* @precondition ???
* @return the value stored at node first
*/
public int getFirst() {
    //method body
}


  • What do you think the postcondition will be for the following List method:

/**
* Creates a new first element
* @param data the data to insert at the
* front of the list
* @postcondition ???
*/
public void addFirst(int data) {
    //method body
    }


Wrap Up
  • Answer the review questions on Canvas for today's lesson

Upcoming Assignments

  • Lab 1: Due Monday at midnight
  • Study for your Quiz