CHAPTER 131 — Unordered Linked List

Data structures are fundamental to programming, and linked lists are a foundational type of data structure. This chapter discusses how a linked list can be implemented as an object. The object has methods that manipulate the nodes of the list.

The LinkedList class of this chapter implements an unordered linked list of integers. The things you can do with this linked list of integers could just as easily be done with an ArrayList of Integers, but more complex data structures are hard to do using arrays.

In practical applications,developers typically use Java's built-in LinkedList class from the Collections Framework. However, building one from scratch is valuable for understanding the underlying mechanics.

The essential concepts of this chapter are how a data structure is built by linking nodes together, and how the methods that maintain the data structure may be members of an object that represents the entire structure.

In this chapter, the integers in the list are not kept in any order. Methods attach new nodes to the list without regard to order. An ordered linked list keeps its data in ascending (or descending) order. The insert method for such a list must find the correct place in the list for a new node. This is the subject of the next chapter.