Chapter: Data Structure and Algorithms

Topic: Lists, Linked Lists and Stacks

Download The Lists Data Structure Class Notes from hamilton.bell.ac.uk

Download The Linked List Teacher's Presentation (PowerPoint Slides) from cs.sunysb.edu

Download The Power Point Slides for The Lists, Stacks and Queues

Take a MCQ Test on Data Structures: Lists, Stacks, and Queues

Visit Dictionary of Algorithms and Data Structures

List Data Structure

A list is a sequential data structure, i.e. a collection of items accessible one after another beginning at the head and ending at the tail. It is a widely used data structure for applications which do not need random access. It differs from the stack and queue data structures in that additions and removals can be made at any position in the list.  

Operations 

The main primitive operations of a list are known as: 

Add - adds a new node  

Set - updates the contents of a node 

Remove - removes a node 

Get - returns the value at a specified index 

IndexOf -returns the index in the list of a specified element 

Additional primitives can be defined: 

IsEmpty - reports whether the list is empty 

IsFull - reports whether the list is full 

Initialise - creates/initialises the list 

Destroy - deletes the contents of the list (may be implemented by re-initialising the 

list)