Chapter 11 Linked Data Structures Linked Lists 1 Analogy When you are waiting in line for a movie or at a bank the ordering of the line is maintained by physical contiguity That is you know where you are in the overall ordering by your physical position in the queue When a person in front of you leaves the line you move up physically and if someone breaks into the line ahead of you you may have to step back Thus changes in the line affect not only where you are in line but your physical location as well The waiting line at an admittedly idealized barbershop is very different A customer enters the shop picks up an old copy of Field and Stream and sits down in an empty chair The location of the seat has nothing to do with the ordering When the barber is ready for the next customer only that one person moves And while the order of the waiting line is completely and unambiguously maintained no individual in the shop may know the entire ordering How does this work For simplicity let s assume a shop with only one barber The shop opens and the first customer say Joe enters Since no one is waiting Joe immediately sits in the barber chair and begins to get his hair cut Then a new customer Sue enters Joe notes that Sue is to be next Sue sits and begins to read but keeps an eye on the door To maintain the proper waiting order she wants to make sure that she gets served before whoever enters the shop next Then Bill arrives Sue notes that Bill follows her She can now devote her entire attention to the magazine while Bill sits down and watches the door Next Alice enters Bill notes that Alice is next Alice watches the door Finally Pat enters Alice notes that Pat is next Pat now assumes the door watch This all can be shown graphically as follows Joe Sue Bill Alice 2001 Donald F Stanat and Stephen F Weiss Pat door Chapter 11 Linked Lists Page 2 When Joe finishes with his haircut he gets up and tells Sue to take his place in the chair Note that only Sue has to move none of the other customers needs to change seats in order to maintain the ordering If all customers follow this discipline the correct ordering will be maintained even though no one person knows the complete ordering For example Alice knows that Pat follows her and that Sue and Bill were in the shop before she arrived but she does not know the ordering of Sue and Bill 2 Linked Lists A sequence whose structure is maintained as a collection of items each of which contains a pointer to the next item is called a linked list The most common form of a linked list has three important features 1 There is a provision for finding the first entry of the list In the barbershop the first entry in the current list is the one in the barber chair Anyone entering the shop would know very little about the complete ordering of customers but would know that the person in the chair is at the head of the list 2 Each entry in the list keeps track explicitly of its successor Thus some local information about the structure of the list is kept with each entry of the list The information specifying a successor is called a pointer or a link 3 The last entry of the list has no successor This is represented by a special pointer value a pointer value that doesn t point to anything Each element of a linked list is called a node and each node contains at least two kinds of data an entry of the data sequence e g the customers in a queue and the structure information that specifies for each entry of the data sequence which node comes next The global structure of the list need not be and generally is not stored anywhere it is distributed throughout the list and consists of the collection of local information in the form of pointers The distribution of the list structure information through the list has some advantages and disadvantages For example getting to the tenth element of an array is easy because we can access it directly using the array index But getting to the tenth element of a linked list requires that we start at the beginning and trudge down ten entries following the link at each one On the other hand insertion into the middle of a list stored in an array requires that we shift some of the array entries while an insertion into the middle of a linked list requires only changes to adjacent entries in the list In this chapter we will look at various forms of linked lists at their implementations and at the algorithms to maintain and manipulate them Arrays are structures that give immediate access to any component Thus to access any entry of an array one needs only know the address of the array the description of its structure the number of dimensions and the number of index values along each dimension and the size of each entry This information is all specified in the definition of an array and is used to provide 1 access to each entry of the array Arrays are called implicit data structures because the structure of an array that is how to access its component parts is specified by the array definition no structure information appears in the array itself Implicit data structures have the advantage of providing quick access to the parts of a data structure but the disadvantage that the structure is fixed Printed January 14 2019 06 56 AM Chapter 11 Linked Lists Page 3 In contrast data in which structure information is itself part of the data is called an explicit data structure Explicit data structures generally require more storage because of the structure information they include but they provide a flexibility that is lacking in the implicit structures Explicit data structures are commonly used in combination with dynamic storage allocation which provides additional storage on demand during program execution The combination of linked structures and dynamic storage allocation makes possible data structures that are not fixed and in fact can grow and change during program execution An example of such an explicit data structure is the linked list in which each entry in a sequence is stored in a node along with information about which node contains the next sequence entry thus the information that determines the list structure is distributed throughout the data structure Linked lists and other linked structures can be implemented in a variety of ways including with arrays But array implementation of linked list is not truly dynamic the list can grow and shrink but only within the bounds of the array We will focus instead on truly dynamic data structures Two