CMPSC 122 Chapter Notes - Chapter 7: Doubly Linked List, Linked List, Royal Institute Of Technology

• School: PSU
• Department: Computer Science
• Course: CMPSC 122
• Professor: Christman Roger

Document Summary

Collection of nodes that form a sequence. Each node stores a reference to the next element of the sequences as well as a value. First and last node are head and tail respectively. Starting at the head, the list can be traversed to the tail. The tail can be identified by a reference to none where a node would usually be. Traversing is also known as link or pointer hopping. Individual elements cannot be accessed by subscript. Stack: first in last out data structure. Add to the tail and remove from the tail. Queue: first in first out data structure. Add to the tail remove from the head or vice versa. What would normally be the tail links back to the head. Good for data sets that do not have a clearly defined beginning or end. Maintain a reference to a particular node, usually called current. Nodes contain references to previous and next nodes in chain.