Linked Lists I

Tom Kelliher, CS23

Mar. 12, 1996

• Collect designs.

• Exam problems:
  1. Classes.

  2. Unix.

  3. Pointers and dynamic memory allocation.

  4. Programming problem involving use of lists.

  5. Recursion.

  Solve four of five.

A Simple Example: Integers on a List

Array Implementation

Declaration file:

#ifndef __ALIST_H
#define __ALIST_H

const int MAX = 100;

class List
{
 public:
   List(void) { size = 0; }
   void Insert(int newValue);   // add newValue to "beginning" of list
   int Delete(void);       // return and delete "first" item on list
   void Print(void);       // print list

 private:
   int size;   // number of items in list
   int items[MAX];
};

#endif

Implementation file:

#include <assert.h>
#include <iostream.h>
#include <iomanip.h>
#include "alist.h"

void List::Insert(int newValue)
{
   assert (size != MAX);
   items[size++] = newValue;
}

int List::Delete(void)
{
   assert (size != 0);
   return items[--size];
}

void List::Print(void)
{
   for (int i = size - 1; i >= 0; --i)
      cout << setw(10) << items[i] << endl;
}

How do we choose the size of MAX?

How do we add to the middle of the list?

Pointer-Based Implementation

Declaration file:

#ifndef __PLIST_H
#define __PLIST_H

#include <stdlib.h>
struct listItem
{
   listItem* next;
   int value;
};

typedef listItem* listPointer;

class List
{
 public:
   List(void) { list = NULL; }
   ~List();
   void Insert(int newValue);   // add newValue to "beginning" of list
   int Delete(void);       // return and delete "first" item on list
   void Print(void);       // print list

 private:
   listPointer list;
};

#endif

Implementation file:

#include <iostream.h>
#include <iomanip.h>
#include <assert.h>
#include <stdlib.h>
#include "plist.h"

List::~List()
{
   listPointer temp;

   while (list != NULL)
   {
      temp = list;
      list = list->next;   // unlink first item on list
      delete temp;         // delete it
      temp = NULL;
   }
}

void List::Insert(int newValue)
{
   listPointer temp = new listItem;
   assert (temp != NULL);

   temp->next = list;
   list = temp;
   temp->value = newValue;
}

int List::Delete(void)
{
   listPointer temp;
   int returnVal;   // value of first list item

   assert (list != NULL);
   returnVal = list->value;   // get value of first list item
   temp = list;
   list = list->next;   // unlink first list item
   delete temp;         // delete first list item
   temp = NULL;
   return returnVal;
}

void List::Print(void)
{

   for (listPointer i = list; i != NULL; i = i->next)
      cout << setw(10) << i->value << endl;
}

Memory overhead?

How do we add to the middle of the list?

Linked List Client

#include <iostream.h>

#ifdef POINTERS

#include "plist.h"

#else

#include "alist.h"

#endif

int main()
{
   List l;

   l.Insert(4);
   l.Insert(39);

   l.Print();

   cout << "Deleted " << l.Delete() << endl;

   l.Print();

   return 0;
}

Compiling?

Comparison

• Memory space
• Execution time

The ADT List

Operations:

• CreateList()
• DestroyList()
• ListIsEmpty()
• ListLength()
• ListInsert(NewPosition, NewItem, Success)
• ListDelete(Position, Success)
• ListRetrieve(Position, DataItem, Success)

ListIsEmpty()

int List::ListIsEmpty(void)
{
   return list == NULL;
}

ListLength()

int List::ListLength(void)
{
   int len = 0;
   listPointer temp = list;

   while (temp != NULL)
   {
      ++len;
      temp = temp->next;
   }

   return len;
}

Tradeoffs?

ListInsert()

void ListInsert(int newPosition, int newItem)
{
   listPointer newI;

   assert (1 <= newPosition && newPosition <= ListLength() + 1);

   if (newPosition == 1)
   {
      newI = new listItem;
      assert (newI != NULL);

      newI->next = list;
      newI->value = newItem;
      list = newI;
   }
   else
   {
      listPointer temp = list;

      newI = new listItem;
      assert (newI != NULL);

      while (newPosition > 2)
      {
         --newPosition;
         temp = temp->next;
      }

      newI->next = temp->next;
      newI->value = newItem;
      temp->next = newI;
   }
}

Exercise

Try the remaining List methods on your own.