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

42

-3

17

9

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

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) {
        this.data = data;
        this.next = next;
    }
}

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!