A linked list is a data structure that is similar to an array in that the elements are stored in a linear order. However unlike an array, in which the order is determined by array indices, the order in a linked list is governed by pointers, which allows for the dynamical allocation of data. A singly linked list consists of a sequence of records each of which contains some data as well as a pointer NEXT which points to the next record in the sequence. If X is the last record, then NEXT[X] is a nil pointer. A special pointer, called HEAD points to the first element of the linked list. If HEAD is nil then the list is empty. A variant of a singly linked list is a doubly linked list which contains for each record X an additional pointer PREV[X] that points...