Submit deadline: 16:00, 25 September 2024, Wednesday

What you need to accomplish in this lab:

Implement a capacity limited singly linked list using array as its concrete data structure.

The interface of such a singly linked list that stores double numbers is shown below:

linkedlist.h
class LinkedList {
  public:
    // constructor
    LinkedList(int capacity);

    // ignore duplicates, returns false if list already full;
    bool insert(double newData); 

    // return the index of the array cell that contains parameter data
    // or return -1 if data doesn't exist in the list
    int find(double data);

    // return false if oldData doesn't exist in the list
    // or if the list already full
    bool insertAfter(double oldData, double newData);

    // return false if data doesn't exist in the list
    bool remove(double data);

    // for testing purposes, display all data in the list
    void traverse();

    // destructor
    ~LinkedList();

  private:
    struct Cell {
        double data; // data part of the linked list node
        int next;    // link part of the linked list node
    };
    // suggested data fields
    int capacity;
    int size; // optional
    Cell *nodes;
    int freeListHead;
    int listHead;
};

linkedlist.cpp
    // constructor
LinkedList::LinkedList(int capacity)
{
    this->capacity = capacity;
    assert(capacity > 0);
    nodes = new Cell[capacity];
    size = 0;
    freeListHead = 0; 
    listHead = -1;
    for(int i = 0; i < capacity-1; i++)
        nodes[i].next = i+1; 
    nodes[capacity-1].next = -1;
}

    // ignore duplicates, returns false if list already full;
bool LinkedList::insert(double newData)
{
    if (freeListHead == -1)
        return false;

    int newNode = freeListHead;
    freeListHead = nodes[freeListHead].next;

    nodes[newNode].data = newData;
    nodes[newNode].next = listHead;
    listHead = newNode;

    return true;
} 

    // return the index of the array cell that contains parameter data
    // or return -1 if data doesn't exist in the list
int LinkedList::find(double data)
{
    int curr = listHead;
    while (curr != -1 && nodes[curr].data != data)
        curr = nodes[curr].next;
    return curr;
}

    // return false if oldData doesn't exist in the list
    // or if the list already full
bool LinkedList::insertAfter(double oldData, double newData)
{
    if (freeListHead == -1)
        return false;
    int prev = find(oldData);
    if (prev == -1)
        return false;

    int newNode = freeListHead;
    freeListHead = nodes[freeListHead].next;

    nodes[newNode].data = newData;
    nodes[newNode].next = nodes[prev].next;
    nodes[prev].next = newNode;
    return true;
}

    // return false if data doesn't exist in the list
bool LinkedList::remove(double data)
{
    int prev = -1;
    int curr = listHead;
    while (curr != -1 && nodes[curr].data != data) {
        prev = curr;
        curr = nodes[curr].next;
    }

    if (curr == -1)
        return false;

    if (prev == -1) {
        listHead = nodes[curr].next;
    } else {
        nodes[prev].next = nodes[curr].next;
    }

    nodes[curr].next = freeListHead;
    freeListHead = curr;

    return true;
}

void LinkedList::traverse()
{
    if (listHead == -1) {
        cout << "The list is empty.\n";
    } else {
        cout << "The list contains the following data: \n"
        int curr = listHead;
        while (curr != -1) {
            cout << nodes[curr].data << " ";
            curr = nodes[curr].next;
        }
        cout << endl;
    }
}

    // destructor
LinkedList::~LinkedList()
{
    delete [] nodes;
}

Submit your work using the submit name Lab2. The submit script for this lab accepts *.h, *.cpp, *.txt and makefile.