3.2.3 Lists and Pointers

2.3 Lists & Pointers

Abstract Data Types

•       Programming Languages use Data Types such as : Integer, Real, String, Date etc…

•       Abstract Data Type – a data type whose properties are specified independent of any programming language.

•       For example -                   

•       List –     a collection of elements with an                inherent order.

List Operations

These operations are required for a list:

•       Initialise List

•       Insert Element

•       Find Element

•       Delete Element

•       Length of List

•       Output the List

Types of List

Linear List

•       Items are stored in linear order in the list.

•       Linear lists are simple, but slow and inefficient.

Linked List

•       Items are stored in the next available space and pointers used to link the elements.

•       Linked Lists are complex to code but fast and efficient to use.

Inserting an Element into a Linked List

Pointer

A variable that contains an address.  The Pointer points to the memory location with that address.

Null Pointer

A pointer that points to nothing.  Usually Ø or -1

Programming Linked Lists

•       Linked Lists can be programmed using 2 dimensional arrays. 

•       New values can be inserted without shifting any other values.

•       Value can still be output in order.