Monash University > CSSE > CSE1303 > Part A > Lectures > Lecture A09 notes

CSE1303 Computer Science
Semester 2 2003
Part A
Lecture A09 notes: Linked Lists

In this lecture

• Kruse 5.2.2 - 5.2.5
• Standish 2.4 - 2.5

• when the records are small
• when the size of the list is known before the program is run
• when there are few insertions or deletions made except at the end of the list
• when random access is important

• when the size of the list needed is not known in advance
• when flexibility is needed in inserting, deleting, and rearranging the items in the list

• Can traverse the list in both directions - greater flexibility.

Code for this lecture

/* linkList.h */
#ifndef LINKLISTH
#define LINKLISTH

#include <stdbool.h> 
#include "node.h"

struct LinkedListRec
{
 int      count;
 Node*    headPtr;
};

typedef struct LinkedListRec     List;

void intializeList(List* listPtr);
bool listEmpty(const List* listPtr);
Node* setPosition(const List* listPtr, int position);
void insertItem(List* listPtr, float item, int position);
void deleteNode(List* listPtr, int position);
int listSize(const List* listPtr);
void clearList(List* listPtr);
void printList(const List* listPtr);

#endif

/* linkList.c */
#include <stdio.h>
#include <stdlib.h>
#include "linkList.h"

/* Initialize a list to be empty. */
void initializeList(List* listPtr)
{
 listPtr->headPtr = NULL;
 listPtr->count = 0;
}

/*  Given a position, this function returns a pointer
 *  to the node in that position in the list.  */
Node* setPosition(const List* listPtr, int position)
{
 int   i;
 Node* nodePtr = listPtr->headPtr;

 if (position < 0 || position >= listPtr->count)
 {
   fprintf(stderr, "Invalid position\n");
   exit(1);
 }
 else {
   for (i = 0; i < position; i++)
   {
     nodePtr = nodePtr->nextPtr;
   }
 }
 return nodePtr;
}

/* Insert an item at a position in the Linked List. */
void insertItem(List* listPtr, float item, int position)
{
 Node* newNodePtr = makeNode(item);
 Node* prevPtr = NULL;

 if (position == 0)
 {
    newNodePtr->nextPtr = listPtr->headPtr;
    listPtr->headPtr = newNodePtr;
 }
 else
 {
    prevPtr = setPosition(listPtr, position-1);
    newNodePtr->nextPtr = prevPtr->nextPtr;
    prevPtr->nextPtr = newNodePtr;
 }
 listPtr->count++;
}

/* Delete the node at a position in the Linked List. */
void deleteNode(List* listPtr, int position)
{
 Node* oldNodePtr = NULL;
 Node* prevPtr = NULL;

 if (!listEmpty(listPtr) && position < listPtr->count)
 {
   if (position == 0)
   {
     oldNodePtr = listPtr->headPtr;
     listPtr->headPtr = oldNodePtr->nextPtr;
   }
   else
   {
     prevPtr = setPosition(listPtr, position-1);
     oldNodePtr = prevPtr->nextPtr;
     prevPtr->nextPtr = oldNodePtr->nextPtr;
   }
   listPtr->count--;
   free(oldNodePtr);
 }
 else
 {
    fprintf(stderr, "List is empty or invalid position\n");
    exit(1);
 }
}

/* doubleLinkList.h */
#ifndef DOUBLELINKLISTH
#define DOUBLELINKLISTH

struct DoubleLinkNodeRec
{
 float                       value;
 struct DoubleLinkNodeRec*   nextPtr;
 struct DoubleLinkNodeRec*   previousPtr;
};

typedef struct DoubleLinkNodeRec Node;

struct DoubleLinkListRec
{
 int    count;
 Node*  currentPtr;
 int    position;
};

typedef struct DoubleLinkListRec List;

Node* makeNode(float item);
void intializeList(List* listPtr);
bool listEmpty(const List* listPtr);
Node* setPosition(List* listPtr, int position);
void insertItem(List* listPtr, float item, int position);
void deleteNode(List* listPtr, int position);
int listSize(const List* listPtr);
void clearList(List* listPtr);
void printList(const List* listPtr);

#endif

[ Top | Home ]
Last Updated: Wednesday 27 August 2003 10:46:35