Link Search Menu Expand Document

Linked Nodes

Table of contents

  1. DNA Strand
  2. Linked nodes

DNA Strand

In the context of programming, main memory refers to the temporary workspace that is used by currently-running programs. Main memory works like a very large array. When we create a new int[10], Java communicates with the operating system to reserve a chunk of main memory large enough to fit 10 integers. This chunk of memory is contiguous: all of the items are next to each other with no gaps in between.

Say we want to represent a list of the following numbers, [42, -3, 17, 9].

Contiguous memory

In an ArrayIntList, the i-th item in the list is always stored at elementData[i]. As a result, ArrayIntList can provide fast access to the value at any particular index so methods like get are constant-time operations. But maintaining this invariant slows down removeFront or remove-in-the-middle, which can be important for efficiently modeling and simulating biological data.

Computational biology is an interdisciplinary area of computer science focused on programming computers to understand biological data, such as DNA, the carrier of genetic information in living things. Each DNA strand is made up of smaller units called nucleotides. There are four different nucleotides present in DNA: A, C, G, and T. Every human cell has billions of nucleotides, some of which are the same (or at least very similar) across almost all humans while other portions vary across the population. Computer programs can be used to analyze DNA for criminal justice and to simulate biological processes for scientific research.

DNA Strand

Oct 19
BJP 16.2
  1. Designate private visibility to encapsulate nested classes.
  2. Trace the execution of programs with nested object references.
  3. Apply the standard traversal pattern to loop over each item stored in linked nodes.
Oct 20
Oct 21
BJP 16.3
  1. Define methods that handle the empty, front, middle, and end linked node cases.
  2. Explain why LinkedList (unlike ArrayList) implements the Queue interface.
Oct 22
Oct 23
Recursive Tracing
BJP 12.1, 12.2
  1. Trace the execution of programs with method calls by transferring control.
  2. Trace the execution of programs using stack frames each with their own variables.
  3. Trace the execution of programs with a single recursive call.

What would a list implementation look like if it was not represented in terms of contiguous memory? In non-contiguous memory, elements can be stored anywhere. One possibility is shown below.

Non-contiguous memory (one possibility)
42  9 -3  17

Non-contiguous memory provides more flexibility since an item can be added anywhere. It’s now much more difficult to know the location of the next element in the list. Collections based on non-contiguous memory address this problem by storing two pieces of information per element:

  1. The actual data value of the element.
  2. A reference to the next element in the list.

Linked nodes

Linked nodes are a non-contiguous memory data structure, which we represent in Java by defining a ListNode class. Each ListNode maintains two fields.

  1. The actual data value of the element.
  2. A reference to the next element in the list.
public class ListNode {
    public int data;
    public ListNode next;

    public ListNode(int data) {
        // Construct a ListNode with the ListNode(data, next) constructor
        this(data, null);

    public ListNode(int data, ListNode next) { = data; = next;
How can a ListNode also contain a field of type ListNode?

Remember that Java stores references to objects, not the objects themselves. The value of a ListNode variable is a reference to a ListNode object somewhere else in memory.

An analogy could be to think about browsing websites online. Many websites often have a link back to the home page (typically the website’s logo), even on the home page itself. There’s no problem with this circular setup since we don’t follow a link until it is clicked. In the same way, Java does not follow references until a program requests its value.

Note that the fields of the ListNode class are declared public. In most programming situations, this would expose the ListNode implementation to the client, thus breaking our public method encapsulation and external correctness guarantees. But in this case, we can make sure that the client never knows about the ListNode class by defining it as a private static class nested inside a public LinkedIntList class. Earlier, we solved queue ADT problems using the LinkedList class without knowing about linked nodes because of this encapsulation!