Chapter 9.2.2 Linked Lists | Introduction to Programming Using Java

Chapter 9.2.2 Linked Lists | Introduction to Programming Using Java

 

9.2.2 Linked Lists

 

For most of the examples in the rest of this section, linked lists will be constructed out of objects belonging to the class Node which is defined as follows:

Chapter 9.2.2 Linked Lists | Introduction to Programming Using Java

The term node is often used to refer to one of the objects in a linked data structure. Objects of type Node can be chained together as shown in the top part of the above picture. Each node holds a String and a pointer to the next node in the list (if any).

The last node in such a list can always be identified by the fact that the instance variable next in the last node holds the value null instead of a pointer to another node. The purpose of the chain of nodes is to represent a list of strings.

 

Chapter 9.2.2 Linked Lists | Introduction to Programming Using Java

 

The first string in the list is stored in the first node, the second string is stored in the second node, and so on. The pointers and the node objects are used to build the structure, but the data that we are interested in representing is the list of strings.

Of course, we could just as easily represent a list of integers or a list of JButtons or a list of any other type of data by changing the type of the item that is stored in each node.

Although the Nodes in this example are very simple, we can use them to illustrate the common operations on linked lists. Typical operations include deleting nodes from the list, inserting new nodes into the list, and searching for a specified String among the items in the list.

We will look at subroutines to perform all of these operations, among others.

 

Chapter 9.2.2 Linked Lists | Introduction to Programming Using Java

 

For a linked list to be used in a program, that program needs a variable that refers to the first node in the list. It only needs a pointer to the first node since all the other nodes in the list can be accessed by starting at the first node and following links along the list from one node to the next.

In my examples, I will always use a variable named head, of type Node, that points to the first node in the linked list. When the list is empty, the value of head is null.

Chapter 9.2.2 Linked Lists | Introduction to Programming Using Java

SEE MORE:

 

Leave a Comment