1 Analogy2 Linked Lists3 Description of a linked list4 Working with linked lists5 Java implementation of a linked list5.1 Common pitfalls of linked structures6 The ADT List7 Using copying to simplify insertions and deletions7.1 Insertion7.2 Deletion8 Variations on the basic linked list8.1 Eliminating the special cases: dummy head and tail nodes8.2 Circular linked list8.3 Doubly Linked Lists8.4 Multiple access8.4.1 Tail pointers8.4.2 Thumb index8.5 Summary9 Non-linear linked structures: trees and graphsChapter 11Linked Data Structures: LinkedLists1 AnalogyWhen you are waiting in line for a movie or at a bank, the ordering of the line is maintained byphysical contiguity. That is, you know where you are in the overall ordering by your physicalposition in the queue. When a person in front of you leaves the line, you move up physically, and ifsomeone breaks into the line ahead of you, you may have to step back. Thus changes in the lineaffect 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 theshop, picks up an old copy of Field and Stream, and sits down in an empty chair. The location ofthe seat has nothing to do with the ordering. When the barber is ready for the next customer, onlythat one person moves. And while the order of the waiting line is completely and unambiguouslymaintained, 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, sayJoe, enters. Since no one is waiting, Joe immediately sits in the barber chair and begins to get hishair cut. Then a new customer, Sue, enters. Joe notes that Sue is to be next. Sue sits and begins toread, but keeps an eye on the door. To maintain the proper waiting order, she wants to make surethat she gets served before whoever enters the shop next. Then Bill arrives. Sue notes that Billfollows her. She can now devote her entire attention to the magazine while Bill sits down andwatches 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 showngraphically as follows.Joe Sue Bill Alice Pat door© 2001 Donald F. Stanat and Stephen F. WeissChapter 11 Linked Lists Page 2When Joe finishes with his haircut, he gets up and tells Sue to take his place in the chair. Note thatonly Sue has to move; none of the other customers needs to change seats in order to maintain theordering. If all customers follow this discipline, the correct ordering will be maintained eventhough no one person knows the complete ordering. For example, Alice knows that Pat followsher, and that Sue and Bill were in the shop before she arrived, but she does not know the orderingof Sue and Bill. 2 Linked ListsA sequence whose structure is maintained as a collection of items, each of which contains a pointerto the next item, is called a linked list. The most common form of a linked list has three importantfeatures:1. There is a provision for finding the first entry of the list. In the barbershop, the first entryin the current list is the one in the barber chair. Anyone entering the shop would know verylittle about the complete ordering of customers, but would know that the person in thechair is at the head of the list. 2. Each entry in the list keeps track explicitly of its successor. Thus, some local informationabout the structure of the list is kept with each entry of the list. The information specifyinga 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: anentry of the data sequence (e.g., the customers in a queue) and the structure information thatspecifies (for each entry of the data sequence) which node comes next. The global structure of thelist need not be (and generally is not) stored anywhere, it is distributed throughout the list andconsists of the collection of local information in the form of pointers. The distribution of the list structure information through the list has some advantages anddisadvantages. For example, getting to the tenth element of an array is easy because we can accessit directly using the array index. But getting to the tenth element of a linked list requires that westart at the beginning and trudge down ten entries, following the link at each one. On the otherhand, insertion into the middle of a list stored in an array requires that we shift some of the arrayentries, while an insertion into the middle of a linked list requires only changes to adjacent entriesin 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 ofan array, one needs only know the address of the array, the description of its structure (the numberof 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 toeach 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 structureinformation appears in the array itself. Implicit data structures have the advantage of providingquick access to the parts of a data structure, but the disadvantage that the structure is fixed. Printed January 14, 2019 06:56 AMChapter 11 Linked Lists Page 3In contrast, data in which structure information is itself part of the data is called an explicit datastructure. Explicit data structures generally require more storage because of the structureinformation 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 oflinked structures and dynamic storage allocation makes