7
\$\begingroup\$

A program to simulate a linear linked list using an array:

Specs:

A y : Create a new node with data value y, and append this node to L

I x y : Find the node t with value x, create a new node p with data value y, and insert node p after t in L

D y : Find the node with data value y, and delete that node from L

R : Reverse L

T : Output all data values in L

Sample Input/Output:

A 5 
A 1 
I 5 4 
I 1 9 
A 7 
I 9 8 
D 9 
D 8 
T 
5 4 1 7
R
T
7 1 4 5

My implementation:

// A program to simulate a linear linked list using an array
/*********************************************************************************************************************/

#include <iostream>
#include <string>

using namespace std;

struct node {
   int data;
   int prev;
   int next;

   // Constructor: 
   node() {
      data = -1;
      prev = -1;
      next = -1;
   }
};

node A[100];    // Array of nodes used to simulate the linked list      
int slot = 1;   // Array index of the next free space (beginning from index 1 initially)
int head = -1;  // Array index of the starting element in the list (-1 implies no entries yet)
int tail = -1;  // Array index of the tail in the list
int elements = 0;   // Number of elements in the list

// Function prototypes:
void insert(int);
void insertAfter(int,int);
void deleteElement(int);
void reverse();
void print();
int findIndex(int);


int main() {
    int a, b;
    char c;
    cout << "Please input the instructions (enter 'E' to exit): \n";


    do {
        cin >> c;
        switch(c) {
                case 'A':   cin >> a;
                            insert(a);
                            break;
                case 'I':   cin >> a >> b;
                            insertAfter(a,b);
                            break;
                case 'D':   cin >> a;
                            deleteElement(a);
                            break;
                case 'R':   reverse();
                            cout << "\nLinked list successfully reversed\n\n"; 
                            break;                      
                case 'T':   print();
                            break;
                case 'E':   cout << "\nExiting program...\n\n";
                            break;            
                default:    cout << "\nInvalid input entered\n\n";          
        }

    } while (c != 'E');

    return 0;
}


void insert(int value) {
    if (slot == -1) {
        cout << "\nNo free space available.\n\n";
    } else {
        elements++;
        A[slot].data = value;
        A[slot].next = 0;
        if (head == -1) {
            // If the list is empty prior to the insertion
            A[slot].prev = 0;
            head = slot;
            tail = slot;
        } else {
            A[tail].next = slot;
            A[slot].prev = tail; 
            tail = slot;    
        }
        cout << endl << "Element \'" << value << "\'"<< " successfully inserted\n\n";


        // Finding the index of the next free location:
        do {
            do {
                slot = (slot + 1) % 100;
            } while(slot == 0); 
            if (A[slot].next == -1) return;
        } while(slot != tail);
        slot = -1;
        cout << "\nNo more free space available. Please delete some elements before inserting new.\n\n";
    }   
}


void insertAfter(int value1,int value2) {
    if (slot == -1) {
        cout << "\nNo free space available.\n\n";
    } else {
        int predecessor = findIndex(value1);

        if (predecessor == -1) {
            cout << "\nElement " << value1 << " not found\n\n";
            return;
        }

        if (A[predecessor].next == 0) {
            // If value1 is the last element in the list
            insert(value2);
            return;
        }

        elements++;
        A[slot].data = value2;
        A[slot].prev = predecessor;
        A[slot].next = A[predecessor].next;
        A[A[predecessor].next].prev = slot;
        A[predecessor].next = slot;
        cout << endl << "Element \'" << value2 << "\'"<< " successfully inserted\n\n";

        // Finding the index of the next free location:
        int temp = slot;
        do {
            do {
                slot = (slot + 1) % 100;
            } while(slot == 0); 
            if (A[slot].next == -1) return;
        } while(slot != temp);
        slot = -1;
        cout << "\nNo more free space available. Please delete some elements before inserting new.\n\n";
    }   
}


void deleteElement(int value) {
    if (head == -1) {
        cout << "\nNo elements to delete.\n\n";
        return;
    }

    if (elements == 1) {
        // Deleting the only element in the list
        A[head].data = -1;
        A[head].prev = -1;
        A[head].next = -1;
        head = -1;
        elements--;
        return;
    }

    int index = findIndex(value); 

    if (index == -1) {
        cout << "\nElement not found.\n\n";
        return;
    }

    if (index == head) {
        // Deleting the first element in the list
        int successor = findIndex(A[A[index].next].data);
        A[successor].prev = 0;
        head = successor;       
        A[index].data = -1;
        A[index].prev = -1;
        A[index].next = -1; 
        cout << endl << "Element \'" << value << "\'"<< " successfully deleted\n\n";
        elements--;                 
        return;
    }

    if (index == slot) {    
        // Deleting the last element in the list
        int predecessor = findIndex(A[A[index].prev].data);
        A[predecessor].next = 0;        
        A[index].data = -1;
        A[index].prev = -1;
        A[index].next = -1; 
        cout << endl << "Element \'" << value << "\'"<< " successfully deleted\n\n";
        elements--;
        return; 
    }

    int successor = findIndex(A[A[index].next].data);
    int predecessor = findIndex(A[A[index].prev].data);
    A[predecessor].next = successor;
    A[successor].prev = predecessor;
    A[index].data = -1;
    A[index].prev = -1;
    A[index].next = -1;
    cout << endl << "Element \'" << value << "\'"<< " successfully deleted\n\n";
    elements--;                     
}

void reverse() {
    int i = head;
    tail = head;
    int temp;
    int hold;
    while (i != 0) {
        hold = i;
        i = A[i].next;

        //swap the previous and next data members to reverse the list:
        temp = A[hold].prev;
        A[hold].prev = A[hold].next;
        A[hold].next = temp;
    }
    head = hold;    
}


void print() {
    cout << "\nThe current list is: ";
    int i = head;
    while (i != 0) {
        cout << A[i].data << " ";
        i = A[i].next;
    }
    cout << endl << endl;
}


int findIndex (int x) {
    // A helper function to return the index of the element x in A
    int i = head;
    while (i != 0) {
        if (A[i].data == x) {
            return i;
        }
        i = A[i].next;
    }
    return (-1);
}

It seems to work fine but I know for a fact that good programmers can easily figure out bugs, so if you can help me find any or suggest improvements, it will be greatly appreciated.

\$\endgroup\$
  • \$\begingroup\$ I just want to note that in production code std::vector is used often to emulate a linked list, because it is often very efficient, and the implementation of all your functions are couple of lines long. \$\endgroup\$ – Vorac May 14 '18 at 15:09
  • \$\begingroup\$ This is a linked list. The fact that you're using array indices as your links rather than ordinary pointers is irrelevant! \$\endgroup\$ – Toby Speight Mar 4 at 9:30
5
\$\begingroup\$
  • For assigning data members in a constructor, it's more common to use an initializer list:

    node()
        : data(-1)
        , prev(-1)
        , next(-1)
    {}
    

    Moreover, you don't really need to initialize data as well. It may even be misinterpreted as an actual data value at the start, which you may not want.

  • Try to avoid global variables unless they're absolutely necessary. In this case, you can wrap them in a class and make each variable private. You can then probably have that node struct within that class.

  • Don't use single-character variable names:

    int a, b;
    char c;
    

    It shouldn't be up to the reader to deduce the usage, plus you may eventually forget this as well. Always use meaningful names for variables to avoid this.

    For loop counter variables, on the other hand, single letters are okay (and would be initialized within the for loop anyway).

  • There's no need for return 0 at the end of main(). This will be done automatically from just this function.

  • Error messages such as "no elements to delete" or "no free space available" should be printed to std::cerr instead.

  • If you're going to hold the user to a static array size, then you should also state this size to the user. A "no free space" warning may instead scare the user into thinking that there's no more memory available to use.

  • There is some duplication in deleteElement(). Since each case will end with a return, use if/else if (starting with the second if) and remove each return statement starting from there. With that, you can just have one elements-- at the very end.

  • Don't put that first print statement in print(). Users may not expect that and not even want it. If it's desired, then they'll put it in their own driver file. In addition, replace the endls with '\n' so that they're not forced to have the buffer flushed as well.

  • Whether or not you're allowed to use library functions, do know that you can just have reverse() call std::reverse():

    void reverse() {
        std::reverse(std::begin(A), std::end(A));
    }
    

    Note: std::begin()/std::end() are under <iterator> and require C++11.

\$\endgroup\$
3
\$\begingroup\$

Bug

When deleting a node, you have this code:

int successor = findIndex(A[A[index].next].data);
int predecessor = findIndex(A[A[index].prev].data);

This is wrong because if there are nodes with the same value in your list, you will find the first occurrence and not the one that you actually want. For example, if your list were:

1 2 1 3 2

and you were deleting the 3, you would end up modifying the wrong successor and predecessor nodes. The correct code is actually much simpler:

 int successor   = A[index].next;
 int predecessor = A[index].prev;

Bug 2

If you delete the tail node, you need to update the tail variable. Right now, you don't do that, so your next insert will do something bad.

Furthermore, your check to see if you are deleting the tail node is wrong. This check:

if (index == slot) {    
    // Deleting the last element in the list

should be:

if (index == tail) {    
    // Deleting the last element in the list

Bad choice of terminator

You use 0 to terminate your list, but 0 is a valid index in your array. This causes you to do a hack to skip over index 0 when finding a free slot. If you used -1 as your terminator, you wouldn't have that problem.

Inefficient free slot finder

Currently, every time you add a node, you need to scan the entire array looking for the next free slot. If you kept all your free nodes in a free list, you could find that free slot instantly.

At initialization time, you set up all your nodes in a single list, and keep the head of that list in a variable freeListHead. Then when you need a free node, you pop the head off the free list. When you delete a node, you push the deleted node onto the front of the free list.

Prev pointer unnecessary

With the given problem statement, there is no need to make your list a doubly linked list. Generally, doubly linked lists are useful when you want to delete a node given the node itself, but you never have to do that.

But since you decided to use a doubly linked list, you could do better than what you've done. Your insertion and removal code would be simpler if you made the list a circular list with head pointing at the first element. If you did that, it would eliminate a lot of special cases, especially with deletion. By circular list, I mean that the tail node's next points at the head node, and the head node's prev points back at the tail node.

Hardcoded limit

It doesn't seem very good to limit yourself to 100 nodes. It would be better if you used malloc() to allocate the first 100 nodes, and then if you ran out of space and needed more nodes, you could call realloc() as necessary. Make sure you use a good reallocation strategy such as doubling the limit every time.

\$\endgroup\$

protected by Community Mar 3 at 9:03

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site (the association bonus does not count).

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.