A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets, supporting (though not necessarily efficiently) all the operations. As shown in Figure 10.3, each element of a doubly linked list L is an object with an attribute key and two other pointer attributes: next and pre . The object may also contain other satellite data. Given an element x in the list, x.next points to its successor in the linked list, and x.pre points to its predecessor. If x.pre = NIL, the element x has no predecessor and is therefore the first element, or head, of the list. If x.next = NIL, the element x has no successor and is therefore the last element, or tail, of the list. An attribute L.head points to the first element of the list. If...
Comments
Post a Comment