Lecture 10 Linked Lists 15 122 Principles of Imperative Computation Spring 2024 Frank Pfenning Rob Simmons Andr Platzer Iliano Cervesato In this lecture we discuss the use of linked lists to implement the stack and queue interfaces that were introduced in the last lecture The linked list implementation of stacks and queues allows us to handle work lists of any length Additional Resources Review slides https cs cmu edu 15122 handouts slides review 10 linkedlist OLI modules https cs cmu edu 15122 handouts oli oli 10 shtml Code for this lecture https cs cmu edu 15122 handouts code 10 linkedlist pdf tgz This fits as follows with respect to our learning goals Computational Thinking We discover that arrays contain implicit infor mation namely the indices of elements which an be made explicit as the addresses of the nodes of a linked list We also encounter the no tion of trade off as arrays and linked lists have different advantages and drawbacks and yet achieve similar purposes Algorithms and Data Structures We explore linked lists a data structure used pervasively in Computer Science and examine some basic algo rithms about them Programming We see that programming algorithms for linked lists can be tricky which exposes once more the power of stating and checking invariant We use linked lists to implement stacks and queues 1 Linked Lists Linked lists are a common alternative to arrays in the implementation of data structures Each item in a linked list contains a data element of some LECTURE NOTES Carnegie Mellon University 2024 Lecture 10 Linked Lists 2 type and a pointer to the next item in the list It is easy to insert and delete elements in a linked list which are not natural operations on arrays since arrays have a fixed size On the other hand access to an element in the middle of the list is usually O n where n is the length of the list An item in a linked list consists of a struct containing the data element and a pointer to another linked list In C0 we have to commit to the type of element that is stored in the linked list We will refer to this data as having type elem with the expectation that there will be a type definition elsewhere telling C0 what elem is supposed to be Keeping this in mind ensures that none of the code actually depends on what type is chosen These considerations give rise to the following definition struct list node elem data struct list node next typedef struct list node list This definition is an example of a recursive type A struct of this type contains a pointer to another struct of the same type and so on We usually use the special element of type t namely NULL to indicate that we have reached the end of the list Sometimes as will be the case for our use of linked lists in stacks and queues we can avoid the explicit use of NULL and obtain more elegant code The type definition is there to create the type name list which stands for struct list node so that a pointer to a list node will be list We could also have written these two statements in the other order to make better use of the type definition typedef struct list node list struct list node There are some restriction on recursive types For example a declara elem data list next tion such as struct infinite int x struct infinite next would be rejected by the C0 compiler because it would require an infinite amount of space The general rule is that a struct can be recursive but the recursion must occur beneath a pointer or array type whose values are addresses This allows a finite representation for values of the struct type Lecture 10 Linked Lists 3 We don t introduce any general operations on lists let s wait and see what we need where they are used Linked lists as we use them here are a concrete type which means we do not construct an interface and a layer of abstraction around them When we use them we know about and exploit their precise internal structure This is in contrast to abstract types such as queues or stacks whose implementation is hidden behind an interface ex porting only certain operations This limits what clients can do but it al lows the author of a library to improve its implementation without having to worry about breaking client code Concrete types are cast into concrete once and for all 2 List segments A lot of the operations we ll perform in the next few lectures are on segments of lists a series of nodes starting at start and ending at end This is the familiar structure of an inclusive lower exclusive upper bound we want to talk about the data in a series of nodes ignoring the data in the last node That means that for any non NULL list node pointer l a segment from l to l is empty contains no data Consider the following structure According to our definition of segments the data in the segment from a1 to a4 is the sequence 3 7 3 the data in the segment from a2 to a3 contains the sequence 7 and the data in the segment from a1 to a1 is the empty sequence Note that if we compare the pointers a1 and a3 C0 will tell us they are not Lecture 10 Linked Lists 4 equal even though they point to locations that contain the same data a1 and a3 point to different locations in memory Given an inclusive beginning point start and an exclusive ending point end how can we check whether we have a segment from start to end The simple idea is to follow next pointers forward from start until we reach end If we reach NULL instead of end then we know that we missed our desired endpoint so that we do not have a segment We also have to make sure that we say that we do not have a segment if either start or end is NULL as that is not allowed by our definition of segments above We can implement this simple idea in all sorts of ways Recursively bool is segment list start list end if start NULL return false if start end return true return is segment start next end Using a while loop bool is segment list start list end list l start while l NULL if l end return true l l next return false Using a for loop bool is segment list start list end for list p start p NULL p p next if p end return true return false However every one of these implementations of is segment has the same problem if given a circular linked list structure the specification function is segment may not terminate It s quite possible to create structures like this intentionally or uninten tionally Here s how we could create a circular linked list in Coin cid 7 cid 6 Lecture 10 Linked Lists list start alloc list …