Next: About this document Up: My Home Page
Recursive and Doubly Linked Lists
Lecture 9
Steven S. Skiena
Recursive List Implementation
The basic insertion and deletion routines for linked lists are more elegantly written using recursion.
PROCEDURE Insert[VAR list: T; value:INTEGER] = [* inserts new element in list and maintains order *] VAR new: T; [*new node*] BEGIN IF list = NIL THEN list:= NEW[T, key := value] [*list is empty*] ELSIF value < list.key THEN [*proper place found: insert*] new := NEW[T, key := value]; new.next := list; list := new; ELSE [*seek position for insertion*] Insert[list.next, value]; END; [*IF list = NIL*] END Insert; PROCEDURE Remove[VAR list:T; value:INTEGER; VAR found:BOOLEAN] = [* deletes [first] element with value from sorted list, or returns false in found if the element was not found *] BEGIN IF list = NIL THEN [*empty list*] found := FALSE ELSIF value = list.key THEN [*elemnt found*] found := TRUE; list := list.next ELSE [*seek for the element to delete*] Remove[list.next, value, found]; END; END Remove;Doubly Linked Lists
Often it is necessary to move both forward and backwards along a linked list. Thus we need another pointer from each node, to make it doubly linked.
List types are analogous to dance structures:
- Conga line - singly linked list.
- Chorus line - doubly linked list.
- Hora circle - double linked circular list.
Extra pointers allow the flexibility to have both forward and backwards linked lists:
type pointer = REF node; node = record info : item; front : pointer; back : pointer; end;Insertion
How do we insert p between nodes q and r in a doubly linked list?
p^.front = r; p^.back = q; r^.back = p; q^.front = p;It is not absolutely necessary to have pointer r, since r = q .front, but it makes it cleaner.
The boundary conditions are inserting before the first and after the last element.
How do we insert before the first element in a doubly linked list [head]?
p^.back = NIL; p^.front = head; head^.back = p; head = p; [* must point to entire structure *]Inserting at the end is similar, except head doesn't change, and a back pointer is set to NIL.
Linked Lists: Pro or Con?
The advantages of linked lists include:
- Overflow can never occur unless the memory is actually full.
- Insertions and deletions are easier than for contiguous [array] lists.
- With large records, moving pointers is easier and faster than moving the items themselves.
The disadvantages of linked lists include:
- The pointers require extra space.
- Linked lists do not allow random access.
- Time must be spent traversing and changing the pointers.
- Programming is typically trickier with pointers.
- About this document ...
Steve Skiena
Thu Sep 25 19:29:15 EDT 1997