3-2-3 Lists and Pointers

Abstract data types

Programming languages distinguish between different data types such as integer, real and string. High-level languages also provide the programmer with data structures such as records and arrays. Object-orientated programming languages allow the declaration of classes, data structures combined with the methods that act on them.

Real-life problems often refer to other structure. Or containers, to store data items and objects, also called elements. Lists are example of the structures. We write shopping lists and to do lists and we can setup playlists on media players. People use an endless number of lists.

Elements can be added and deleted from a list. Therefore a list can grow and shrink. This is known as a dynamic structure. A list is a collection of elements with an inherent order.

The operations that need to be performed on a list are:

• initialise list (I.e. start a new list)
  
• insert an element
  
• find an element
  
• delete an element
  
• get length of list
  
• output entire list

Linear Lists

A linear list stores its elements in adjacent locations. Elements in an array are stored physically in adjacent locations in main memory. When an array is declared, the computer reserves the space for elements. This means the array is a static structure.

Advantages:

• Easy to program.
  
• if elements are stored in key order, a binary search is possible.

Disadvantages:

• Memory locations may be wasted due to arrays being static.
  
• Insertion of an element within an ordered list requires moving elements.
  
• Deletion of an element with a list requires moving elements.

Linked Lists

Imagine list elements sorted wherever there is a space and linked to form a sequence. Each element of the list, known as a node, can be represented as a record of data fields, with an extra field used as a pointer that links a node to the next mode in the list. A special outer, the start pointer, points to the first node of the list. The last node in the limits has a null pointer in the pointer field.

The concept of makes insertion and deletion of elements much less time consuming. Just the pointer fields are changed. To insert a new node at the beginning of the list, the contents of the start variable is copied into the new node's pointer field, then the start variable is set to lint to the new node.

Linked lists can also be stored in an array. But instead of moving nodes to insert and delete elements, the nodes are connected to the pointers and the pointer values are the index of the array location of the node.

Use of Free Memory, the heap, and pointers

Pointer type: a variable of pointer type stores an address or a data value.
Heap: the memory locations available to application programs for dynamic allocations.
Dynamic allocation: memory space is only allocated when required at run time.
Memory leakage: successive calls to allocate memory space are made, but memory locations that are no longer required are not released. Eventually no memory is left in the heap.