Linked List
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 to the previous record. Doubly linked lists are usually easier to traverse and search but inserting and deleting elements from such lists is slightly more complicated because both the NEXT and PREV pointers must be updated consistently.
The two operations of inserting and deleting items from a linked list require a bit of care. Usually an auxiliary pointer, say CURRENT, is used to iterate down the linked list until CURRENT points to the element before which a new element, say NEW is to be inserted into the list. One must set the pointer NEXT[CURRENT]=NEW.
However if one were to do this first, one would lose the rest of the list forever. First the pointer to the rest of the list must be saved in an axiliary pointer TEMP=NEXT[CURRENT]. Then the value of NEXT[CURRENT] can be set equal to NEW. And finally NEXT[NEW]=TEMP will correctly splice NEW into the middle of the linked list. As an exercise, the reader may determine what modifications to need to be made in order to insert an element into a doubly linked list.
Deleting an element from a singly linked list is slightly easier. One iterates forward through the list until one reaches the element before the one to be deleted, again using an auxiliary pointer CURRENT. For example one could use the following pseudocode: while the contents of data record NEXT [CURRENT] is not equal to the record to be deleted and NEXT[CURRENT] is not nil (signifying we have reached the end of the list) then set CURRENT = NEXT [CURRENT]. After this loop we will be ready to delete the next element, as long as it is not nil. Set TEMP = NEXT[CURRENT] to save a pointer to the item to be deleted. Then set NEXT[CURRENT] = NEXT[NEXT[CURRENT]] to make the linked list skip over the item to be deleted. Finally in the end one can free the memory pointed to by TEMP, which is why we saved the item to be deleted. Again, deleting from a doubly linked list is only slightly more complicated, and it is a good exercise for the reader to figure out how to do so.
This is the complete article, containing 501 words
(approx. 2 pages at 300 words per page).
