7.2 Linked Structures

Suppose we have a storage class containing a single data field:

class ListNode :

  def __init__(self, data) :

    self.data = data

and we create an instance of the class

a = ListNode(11)

The result is the creation of the variable a and a storage object that contains the integer value 11:

What happens if we create two more instances of the class?

b = ListNode(52)

c = ListNode(18)

This results in the creation of two additional variables and objects:

Now, suppose we add a second data field to the ListNode class:

class ListNode :

  def __init__(self, data) :

    self.data = data

    self.next = None

and assume the three objects created earlier were actually created using this class. What affect does this have on the memory diagram above? The three objects from the previous example would now have a second data field initialized with None or a null reference, as illustrated below:

Since the next field can contain a reference to any type of object, we can assign to it a reference to one of the other ListNode objects. The next field of the object can store any type of value or a reference to any type of object. So what happens if we assign b to the next field of object a?

a.next = b

This results in object a being linked to object b, as shown here:

And finally, we can link object b to object c:

b.next = c

resulting in a chain of objects, as illustrated below:

If we set b and c to None

b = None

c = None

the two references from b and c are removed and no longer point to the objects:

The result is a linked structure. The two objects previously pointed to by b and c are still accessible via a. For example, suppose we wanted to print the values of the three objects. We can access the other two objects through the next field of the first object:

print(a.data)

print(a.next.data)

print(a.next.next.data)

Question 7.2.1

Given the following linked structure,

what would be the result of executing this statement

print(a.next.next.next.data)

An exception would be raised and the program will abort. The code a.next.next.next refers to the link field in the tail node. The link field in the tail node is null or contains None. You can not access a method or attribute on a None reference.

A linked structure contains a collection of objects called nodes, each of which contains data and at least one reference or link to another node. A linked list is a linked structure in which the nodes are connected in sequence to form a linear list. Figure 7.2.1 provides an example of a linked list consisting of five nodes.

Figure 7.2.1: A singly linked list consisting of five nodes and a head reference.

The last node in the list, commonly called the tail node, is indicated by a null link reference. Most nodes in the list have no name and are simply referenced via the link field of the preceding node. The first node in the list, known as the head node, must be named or referenced by an external variable as it provides an entry point into the linked list. This variable is commonly known as the head reference. The link fields within the individual nodes are known as internal references because they are internal to the structure. Whereas the head reference is known as an external reference. A linked list can also be empty, which is indicated when the head reference is None.

External References
We use the term external reference to indicate those reference variables that point to a node but are not themselves contained within a node as is the case with the link fields. Some external references must be permanent or exist during the lifetime of the linked list in order to maintain the collection of nodes. Others are only needed on a temporary basis in order to perform a specific operation. These temporary external references should be local variables that disappear after the function or method has completed.

A linked list is a data structure that can be used to implement any number of abstract data types. While some languages do provide, as part of their standard library, a generic List ADT implemented using a linked list, we are going to create and work with linked lists directly. Some algorithms and abstract data types can be implemented more efficiently if we have direct access to the individual nodes within the ADT than would be possible if we created a generic linked list class.

Question 7.2.2

What would happen if the head reference variable in our example list above were set to None?

The list would be destroyed. When the reference to the first node is removed, it will deleted automatically. That in turn results in the second node being destroyed since the link field from the node containing value 2 is removed, and so on, until every node in the list is destroyed.

Linked structures are built using fundamental components provided by the programming language, namely reference variables and objects. The linked list is just one of several linked structures that we can create. If more links are added to each node, as illustrated in Figure 7.2.2, we can connect the nodes to form any type of configuration we may need. The tree structure, which organizes the nodes in a hierarchical fashion, is another commonly used linked structure that we explore later in Chapter 14 and Chapter 15.

Figure 7.2.2: An example of a complex linked structure.

In the next several sections, we explore the construction and management of a singly linked list independent of its use in the implementation of any specific ADT. In later sections we then present examples to show how linked lists can be used to implement abstract data types. We also include a number of exercises to provide practice in the construction and management of linked lists.

7.1 Objects and References

Chapter 7. Linked Structures

7.3 Singly Linked Lists