Chapter 13: Linked Structures - Stacks

Chapter Scope

• Object references as links

• Linked vs. array-based structures

• Managing linked lists

• Linked implementation of a stack

Linked Structures

• An alternative to array-based implementations are linked structures

• A linked structure uses object references to create links between objects

• An object reference variable holds the address of an object

• A Person object could contain a reference to another Person object.

• A series of Person objects would make up a linked list.

• Links could also be used to form more complicated, non-linear structures.

Linked Lists

• There are no index values built into linked lists

• To access each node in the list you must follow the references from one node to the next

Person current = first;
while (current != null) {
  System.out.println(current);
  current = current.next;
}

• Care must be taken to maintain the integrity of the links

• To insert a node at the front of the list, first point the new node to the front node, then reassign the front reference

• To delete the first node, reassign the front reference accordingly

• If the deleted node is needed elsewhere, a reference to it must be established before reassigning the front pointer

• So far we've assumed that the list contains nodes that are self-referential (Person points to a Person)

• Often we'll want to make lists of objects that don't contain such references

  • Solution: have a separate Node class that forms the list and holds a reference to the objects being stored

• There are many variations on the basic linked list concept

  • For example, we could create a doubly-linked list with next and previous references in each node and a separate pointer to the rear of the list