Unite 2010GDC ChinaAsia Game Show 2010GDC 2011
|
The Linked ListNow that you understand basic pointer concepts, you may be asking yourself, "What is this linked list thing?" Well, a linked list is a dynamic data structure consisting of records (called nodes) that hold data and are "'linked" to each other by a method determined by the programmer. The most common linking method is through pointers (addresses), such that each record contains the address of the next node in the list in addition to the record's regular data. The first node in the list, called the head, is used as the list's key identifier. You must always keep track of the head of the list. Why? Because it is the starting point that will be used later to retrieve the information that you have stored in the list. Lose the head, and you have lost the entry point to the entire list, particularly in our implementation here of the singly linked list. A list expands and shrinks (hence dynamic data structure) as data is added and deleted, allowing the list to accommodate an arbitrary number of elements. Compare this concept to the allocation of an array, which remains the same size during its lifetime. Figure 1.1 shows a visual example of a singly linked list, which we will be discussing throughout this article.
A linked list is a linear data structure. All operations on the list must begin by accessing the first node on the list, then the second node, then the third node, etc. Compared to arrays, this sequential access can be a significant performance drawback. Arrays can be accessed randomly - ever hear of the binary search algorithm? A linked list node can only be accessed after all preceding nodes have been accessed; this results in slower searching algorithms. There are, however, ways around this by manipulating and modifying the structure of the basic linked list that has been described here. We will explore these in a later part of the series. The main advantage of linked lists is their dynamic nature. A list can grow to be quite big with dynamic allocation. New nodes can be added in between existing nodes with a few simple pointer manipulations, and deletions may be performed with a call to free() and some pointer redirection. Some of the operations that we will be covering on the basic linked list include:
|
|
|
|
