3.3 Linked Lists

   

When our primary interest is to go through a collection of items sequentially, one by one, we can organize the items as a linked list a basic data structure where each item contains the information that we need to get to the next item. The primary advantage of linked lists over arrays is that the links provide us with the capability to rearrange the items efficiently. This flexibility is gained at the expense of quick access to any arbitrary item in the list, because the only way to get to an item in the list is to follow links from the beginning.

Definition 3.2 A linked list is a set of items where each item is part of a node that also contains a link to a node.

We define nodes by referring to nodes, so linked lists are sometimes called self-referent structures. Moreover, although a node's link usually refers to a different node, it could refer to the node itself, so linked lists can also be cyclic structures. The implications of these two facts will become apparent as we begin to consider concrete representations and applications of linked lists.

Normally, we think of linked lists as implementing a sequential arrangement of a set of items: Starting at a given node, we consider its item to be first in the sequence. Then, we follow its link to another node, which gives us an item that we consider to be second in the sequence, and so forth. Since the list could be cyclic, the sequence could seem infinite. We most often work with lists that correspond to a simple sequential arrangement of the items, adopting one of the following conventions for the link in the final node:

  • It is a null link that points to no node.

  • It refers to a dummy node that contains no item.

  • It refers back to the first node, making the list a circular list.

In each case, following links from the first node to the final one defines a sequential arrangement of items. Arrays define a sequential ordering of items as well; in an array, however, the sequential organization is provided implicitly by the position in the array. (Arrays also support arbitrary access by index, which lists do not.)

We first consider nodes with precisely one link, and, in most applications, we work with one-dimensional lists where all nodes except possibly the first and the final each have precisely one link referring to them. This corresponds to the simplest situation, which is also the one that interests us most, where linked lists correspond to sequences of items. We will consider more complicated situations in due course.

Linked lists are primitive constructs in some programming environments, but not in Java. However, the basic building blocks that we discussed in Section 3.1 are well suited to implementing linked lists. Specifically, we use objects for nodes and references to objects for links, as follows:

 class Node    { Object item; Node next; } 

This code is nothing more than Java code for Definition 3.2. We implement linked-list nodes as objects of type Node: each node consists of an item (whose type is unspecified here) and a reference to a node. That is, we use references to nodes to implement links. We shall see more complicated representations in Chapter 4 that provide more flexibility and allow more efficient implementations of certain operations, but this simple representation will suffice for us to consider the fundamentals of list processing. We use similar conventions for other linked structures throughout the book.

Memory allocation is a central consideration in the effective use of linked lists. We have defined a class Node, but we will have many objects that instantiate this class, one for each node that we want to use. Whenever we want to use a new node, we need to create an object of type Node. For example, as for any other class, the line of code

 Node x = new Node(); 

creates an object of type Node and returns a reference to it in x. In Section 3.5, we shall briefly consider how the system goes about reserving memory, because addressing that task is a good application of linked lists (!).

When working with linked structures, it is wise to initialize all the members of each object when we create it. Since invoking a constructor is part of the process of instantiating an object, we can adhere to this policy by assigning values to each data field in every constructor. For example, we might define list nodes with the code

 Class Node    { Object item; Node next;      Node(Object v)        { item = v; next = null; }    } 

so that the statement t = new Node(x); not only reserves memory for a node and assigns a reference to it to t, but also sets the item field of the node to the value v and the next field to the value null. Proper use of constructors helps us to avoid programming bugs associated with uninitialized data.

Now, once a list node is created, how do we refer to the information it comprises its item and its link? We have already seen the basic operations that we need for this task: We simply use the class data field names the item in the node referenced by x (which is an Object) is x.item, and the link (which is a reference to a Node) is x.next. As with all other Java references, we so often need to use the phrase "the node referenced by link x" that we simply say "node x" the link does name the node.

The correspondence between links and Java references is essential, but we must bear in mind that the former is an abstraction and the latter a concrete representation. We can design algorithms that use nodes and links, and we can choose one of many possible implementations of that idea. For example, we could also represent links with array indices, as we shall see at the end of this section.

Figures 3.5 and 3.6 show the two fundamental operations that we perform on linked lists. We can remove any item from a linked list, to make it shrink by 1 in length; and we can insert an item into a linked list at any point, to make it grow by 1 in length. For simplicity, we assume in these figures that the lists are circular and never become empty. We will consider null links, dummy nodes, and empty lists in Section 3.4. As shown in the figures, insertion and deletion each require just two statements in Java. To remove the node following node x, we use the statements

 t = x.next; x.next = t.next; 

or simply

 x.next = x.next.next; 
Figure 3.5. Linked-list deletion

To delete, or remove, the node following a given node x from a linked list, we set t to refer to the node to be removed, then change x's link to t.next. The reference t can be used to refer to the removed node (to add it to some other list, for example). Although its link still refers to a node in the list, we generally do not use such a link after removing the node from the list.

graphics/03fig05.gif

Figure 3.6. Linked-list insertion

To insert a given node t into a linked list at a position following another given node x (top), we set t.next to x.next (center), then set x.next to t (bottom).

graphics/03fig06.gif

To insert node t into a list at a position following node x,we use the statements

 t.next = x.next; x.next = t; 

The simplicity of insertion and deletion is the raison d'êetre of linked lists. The corresponding operations are unnatural and inconvenient in arrays because they require moving all of the array's contents following the affected item.

By contrast, linked lists are not well suited for the find the kth item (find an item given its index) operation that characterizes efficient access in arrays. In an array, we find the kth item simply by accessing a[k]; in a list, we have to traverse k links. Another operation that is unnatural on singly linked lists is "find the item before a given item."

When we remove a node from a linked list using x.next = x.next.next, we may never be able to access it again. In Java, this is no special concern because Java automatically reclaims memory to which there is no reference. In many other systems, it is necessary to inform the system when memory may be used for some other purpose and to pay particular attention to doing so when processing large list objects or large numbers of them. We will revisit this issue in Section 3.5.

We will see many examples of applications of these and other basic operations on linked lists in later chapters. Since the operations involve only a few statements, we often manipulate the lists directly rather than defining methods for inserting, deleting, and so forth. As an example, we consider next a program for solving the Josephus problem which provides an interesting contrast with the sieve of Eratosthenes.

We imagine that N people have decided to elect a leader by arranging themselves in a circle and eliminating every Mth person around the circle, closing ranks as each person drops out. The problem is to find out which person will be the last one remaining (a mathematically inclined potential leader will figure out ahead of time which position in the circle to take).

The identity of the elected leader is a function of N and M that we refer to as the Josephus function. More generally, we may wish to know the order in which the people are eliminated. For example, as shown in Figure 3.7, if N = 9 and M = 5, the people are eliminated in the order 5 1 7 4 3 6 9 2, and 8 is the leader chosen. Program 3.8 reads in N and M and prints out this ordering.

Figure 3.7. Example of Josephus election

This diagram shows the result of a Josephus-style election, where the group stands in a circle, then counts around the circle, eliminating every fifth person and closing the circle.

graphics/03fig07.gif

Program 3.8 uses a circular linked list to simulate the election process directly. First, we build the list for 1 to N: We build a circular list consisting of a single node for person 1, then insert the nodes for people 2 through N, in that order, following that node in the list, using the insertion code illustrated in Figure 3.6. Then, we proceed through the list, counting through M - 1 items, deleting the next one using the code illustrated in Figure 3.5, and continuing until only one node is left (which then points to itself).

The sieve of Eratosthenes and the Josephus problem clearly illustrate the distinction between using arrays and using linked lists to represent a sequentially organized collection of objects. Using a linked list instead of an array for the sieve of Eratosthenes would be costly because the algorithm's efficiency depends on being able to access any array position quickly, and using an array instead of a linked list for the Josephus problem would be costly because the algorithm's efficiency depends on the ability to remove items quickly.

When we choose a data structure, we must be aware of the effects of that choice upon the efficiency of the algorithms that will process the data. This interplay between data structures and algorithms is at the heart of the design process and is a recurring theme throughout this book.

Program 3.8 Circular list example (Josephus problem)

To represent people arranged in a circle, we build a circular linked list, with a link from each person to the person on the left in the circle.

 class Josephus    {      static class Node        { int val; Node next;          Node(int v) { val = v; }        }      public static void main(String[] args)        { int N = Integer.parseInt(args[0]);          int M = Integer.parseInt(args[1]);          Node t = new Node(1);          Node x = t;          for (int i = 2; i <= N; i++)            x = (x.next = new Node(i));          x.next = t;          while (x != x.next)            {              for (int i = 1; i < M; i++) x = x.next;              x.next = x.next.next;            }          Out.println("Survivor is " + x.val);        }    } 

In Java, objects and references to objects provide a direct and convenient concrete realization of the abstract concept of a linked list, but the essential value of the abstraction does not depend on any particular implementation. For example, Figure 3.8 shows how we could use arrays of integers to implement the linked list for the Josephus problem. That is, we could implement links using array indices, instead of references to objects. Linked lists were useful well before constructs such as objects and references to them were available in high-level languages such as Java. Even in modern systems, array-based implementations are sometimes convenient.

Figure 3.8. Array representation of a linked list

This sequence shows a linked list for the Josephus problem (see Figure 3.7), built from two arrays using indices instead of references for links. The index of the item following the item with index 0 in the list is next[0], and so forth. Initially (top three rows), the item for person i has index i-1, and we form a circular list by setting next[i] to i+1 for i from 0 to 8 and next[8] to 0.To simulate the Josephus-election process, we change the links (next array entries) but do not move the items. Each pair of lines shows the result of moving through the list four times with x = next[x], then deleting the fifth item (displayed at the left) by setting next[x] to next[next[x]].

graphics/03fig08.gif

Exercises

graphics/icon01.gif 3.25 Write a method that returns the number of nodes on a circular list, given a reference to one of the nodes on the list.

3.26 Write a code fragment that determines the number of nodes that are between the nodes referenced by two given references x and t to nodes on a circular list.

3.27 Write a code fragment that, given references x and t to nodes on two disjoint circular lists, inserts all the nodes on the list containing node t into the list containing node x, at the point following x.

graphics/roundbullet.gif 3.28 Given references x and t to nodes on a circular list, write a code fragment that moves the node following t to the position following the node following x on the list.

3.29 Modify Program 3.8 so that it maintains a circular list after each node is inserted.

3.30 Give the running time of Program 3.8, within a constant factor, as a function of M and N.

3.31 Use Program 3.8 to determine the value of the Josephus function for M = 2, 3, 5, 10, and N = 103, 104, 105, and 106.

3.32 Use Program 3.8 to plot the Josephus function versus N for M = 10 and N from 2 to 1000.

3.34 Develop a version of Program 3.8 that uses an array of indices to implement the linked list (see Figure 3.8).


   
Top


Algorithms in Java, Part 1-4
Algorithms in Java, Parts 1-4 (3rd Edition) (Pts.1-4)
ISBN: 0201361205
EAN: 2147483647
Year: 2002
Pages: 158

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net