- Forward


Lists (Contiguous and Linked)
An Introduction with Examples in C++


Prof. David Bernstein
James Madison University

Computer Science Department
bernstdh@jmu.edu

Print

Definition of a List
Back SMYC Forward

    List
    Values: Elements of any type.
    Operations:
    Name/Operator Arguments Returns
    Constructor A new instance.
    insert
    element The element to insert into the list
    index The position of the new element
    isEmpty true if the list is empty and false o/w
    remove
    index The position of the element
    retrieve
    index The position of the element
    		The element at the specified position
    size The number of elements in the list

A Contiguous, Fixed-Size Implementation
Back SMYC Forward
  • Approach:
    • Use an array
  • An Observation:
    • Many operations require shuffling
A Node for a Linked Implementation
Back SMYC Forward
cppexamples/linkedlist/Node.hpp
 
A Linked List
Back SMYC Forward
cppexamples/linkedlist/List.hpp
 
Linked List Humor
Back SMYC Forward
/imgs
(Courtesy of xkcd)
Absolute and Relative "Pointers"
Back SMYC Forward
  • Traditional Pointers:
    • When we use traditional pointers in a linked list we are pointing to an absolute address
  • An Alternative Approach:
    • Use an offset from the current memory location (i.e., a relative address
  • Where this Might Arise:
    • An array based implementation that uses relative indexes
Questions to Think About
Back SMYC Forward
  • Are there other operations that you would include?
  • Where might you use operator overloading?
  • Could you create an ADT that provides the services of a stack, queue, and list?
There's Always More to Learn
Back -