Pointer - based implementation

 

The list consists of nodes that are consecutively connected to each other by a pointer part of each.

 

Node is a combination of DATA and LINK.

 

What is Data?

 Is the part where the actual data is stored (usually a structure)

 

 What is a Link?   ( Two ways of implementing )

 It is the  link (pointer) to the next element of the list.

 It could be either

  1.  index to an array element (array implementation)                   

  2.  or a pointer variable containing the address of the  next element (pointer)

Common operations on a pointer linked list :

  1. create a node

  2. destroy a node

  3. insert a node in the list

  4. delete a node

  5. traverse a node

  6. get and set data for a node

Data Declaration as pseudo code for a list of integers in the following algorithm :

Data Declaration

          node {

                      dataType data

                      pointer-to-node next

                    }

pointer-to-node  head,tempPtr

dataType dataelement

Create

 Input

none

Precondition

none

Operation

an empty list is created

Postcondition

the variable head is set to NULL

Return Value

none

 

Data Declaration as C++ code (program)

typedef struct node* ptrtype;

struct node {

                    int data;

                    ptrtype next;

                  };

ptrtype head = NULL;

The next  field is used to link nodes .

 

The head variable is used as external pointer to determine the list's beginning  . Without the head pointer , the memory location of the first node would be lost , resulting in the loss of the list or part of it .

 

fig 4.8( P62 )

 

shows a linked list pointed by a node.

 

Example

head

1000

head ->next

2000

head->data

3

head->next->data

4

head->next->next->data

5

Create a node : request the system for a new area of memory .

 

Destroy (release a node) : release the node to the OS .

  1. Use delete command.

  2. Set the pointer referring to the released node to NULL.

InsertFront

A new node is created , its next field is set to point to the head of the list , and then the head pointer is set to point to the new node.

 fig 4.9 (P63)

 

InsertBack

 

We have 2 ways:

  1. Traverse the list until the end . the last node's next filed is set to point to the new new node .

  2. Use a global tail pointer that points to the last node. This would save the time spent traversing the list . The last node next field and the tail pointer are set to point to the new field .

fig 4.10 ( P 64 )

 

InsertConditional

We have to use 2 pointers , prev and cur .

At any time cur points to the node being examined and prev points one location before .

 

DeleteFront

The head pointer is reset to point to the second node and the first node is released .

fig 4.11(