Nsryjdtyk

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 reversednn"; 

                            break;                      

                case 'T':   print();

                            break;

                case 'E':   cout << "nExiting program...nn";

                            break;            

                default:    cout << "nInvalid input enterednn";          

        }



    } while (c != 'E');



    return 0;

}





void insert(int value) {

    if (slot == -1) {

        cout << "nNo free space available.nn";

    } 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 insertednn";





        // 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.nn";

    }   

}





void insertAfter(int value1,int value2) {

    if (slot == -1) {

        cout << "nNo free space available.nn";

    } else {

        int predecessor = findIndex(value1);



        if (predecessor == -1) {

            cout << "nElement " << value1 << " not foundnn";

            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 insertednn";



        // 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.nn";

    }   

}





void deleteElement(int value) {

    if (head == -1) {

        cout << "nNo elements to delete.nn";

        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.nn";

        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 deletednn";

        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 deletednn";

        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 deletednn";

    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.

• 
  

  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.

  
  

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.

can anyone send me menu driven of linklist through arrays plz