• Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 652
  • Last Modified:

Linked List


// Need checked for correctiveness.  Please advise.  Del

***********************code*******************************

// list.h

#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <fstream>

using namespace std;

//const int CAPACITY = 1024;
typedef int ElementType;

class List {

      // prototype for ouput operator
      ostream &operator << (ostream &out, const List &alist);

public:

      List(int maxSize = 1024);
      ~List();
      // copy constuctor
      List(const List, &origList);
      // assignment operator
      const List &operator = (const List &rightHandSide);
      // list traversal
      void listTraversalNode();
      void printInReverse(Node *Head);   // call function to print list in reverse
      void bubbleSort(int); // boolean function ascending
      // empty operation
      bool empty() const;
      // insert and erase
      void insert(ElementType item, int pos);
      void erase(int pos);
      // output
      void display(ostream &out) const;

private:

      int mySize; // current size of list store in myArray
      //ElementType myArray[CAPACITY]; // array to store list of elements
      int myCapacity; // capacity of array
      ElementType *myArray; // pointer to dynamic array
      
};

class Node {

public:

      ElementType data;
      Node *next;

private:

      NodePointer first;
      int mySize;

};

typedef Node *NodePointer;

#endif

****************

// list.cpp

#include <cassert>
#include <iostream>
#include <fstream>
#include <list>
#include <new>
#include <string>
#include "node.h"

using namespace std;

// definition of class constructor
List::List(int maxSize) : mySize(0), myCapacity(maxSize) {

      myArray = new(nothrow) ElementType[maxSize];
      assert(myArray != 0);

}

// definition of class destructor
List::~List() {

      delete [] myArray;

}

// definition of copy constructor
List::List(const List &origList) : mySize(origList.mySize), myCapacity(origList.myCapacity) {

      // get new array for copy
      myArray = new(nothrow) ElementType[myCapacity];

      if(myArray != 0) // check if memory available

            // copy origList's elements into this new array
            for(int i = 0; i < mySize; i++)
                  myArray[i] = origList.myArray[i];
      else {
            cerr << " Inedaguate memory to allocate storage  for list. \n";
            exit(1);

      }

}

// definition of assignment operator
const List &List::operator = (const List &rightHandSide) {

      // check that not self-assignment
      if(this != &rightHandSide) {
            // allocate new array if necessary
            if(myCapacity != rightHandSide.myCapacity) {
                  delete [] myArray;
                  myCapacity = rightHandSide.myCapacity;
                  myArray = new(nothrow) ElementType[myCapacity];

                  // check if memory available
                  if(myArray == 0) {
                        cerr << " Inadequate memory to allocate stack. \n";
                        exit(1);

                  }

            }
            // copy rightHandSide's list elements into this new array
            mySize = rightHandSide.mySize;

            for(int i = 0; i < mySize; i++)
                  myArray[i] = rightHandSide.myArray[i];

      }
      return *this;

}
                  
// definition of empty
bool List::empty() const {

      return mySize == 0;

}

// definition of display
void List::display(ostream &out) {

      for(int i = 0; i < mySize; i++)
            out << myArray[i] << " ";

}

// definition of output operator
ostream &operator << (ostream &out, const List &aList) {

      aList.display(out);
      return out;

}

// definition of insert
void List::insert(ElementType item, int pos) {

      if(mySize == myCapacity) {
            cerr << " No space for linked list element, terminating execution. \n";
            exit(1);

      }
      if(pos < 0 || pos > mySize) {
            cerr << " Illegal location to insert -- " << pos << ". Linked list unchanged. \n";
            return;

      }

      // first shift array elements right to make room for item
      for(int i = mySize; i > pos; i--)
            myArray[i] = myArray[i - 1];

      // now insert item at postion pos and increase list size
      myArray[pos] = item;
      mySize++;

}

void List::listTraversalNode() {

      ptr = first;

      while(ptr != 0) {
            ptr = ptr -> next; // appropriate statements to process ptr -> data

      }

      newptr = new Node(dataVal); // newptr of type NodePointer

      if(predptr != 0) { // not inserting at front
            newptr -> next = predptr -> next;
            predptr -> next = newptr;

      }
      else { // inserting at front
            newptr -> next = first;
            first = newptr; // reset first

      }

      if(predptr != 0) { // not deleting first node
            ptr = predptr -> next;
            predptr -> next = ptr -> next; // bypass

      }
      else { // deleting first node
            ptr = first;
            first = ptr -> next; // reset first

      }
      delete ptr; // return node to heap

}

// reverse print of list
void List::printInReverse(Node *Head) { // not sure on this one, need checked

        if (Head == 0){
       cout << "List is empty." << endl;
      }
     //int count = 0;
     Node *printPtr = new Node;
       printPtr = Head;

       while(printPtr != 0) {
       
       cout << printPtr -> key << endl;
     printPtr = printPtr->next; //advance pointer to next location in list...
       
       }
 
}

// boolean value function ascending ???
void List::bubbleSort(int nList) {

      for(int i = mySize - 1; i > 0; --i) {
      for(int j =0; x < i; ++j) {
         if(nList[j] > nList[j + 1])
            swap(&nList[j],&nList[j + 1]);
      }
   }
}  

// definition of erase
void List::erase(int pos) {

      if(mySize == 0) {
            cerr << " List is empty \n";
            return;

      }
      if(pos < 0 || pos >= mySize) {
            cerr << " Illegal location to delete -- " << pos << ". List unchanged. \n";
            return;

      }

      // shift array elements left to close the gap
      for(int i = pos; i < mySize; i++)
            myArray[i] = myArray[i + 1];

      // decrease list size
      mySize--;

}

int main() {

      // test the class constructor
      List intList;
      cout << " Constructing intList\n";

      // test empty and output of empty list
      if(intList.empty())
            cout << " Empty: \n" << intList << endl; // test output of empty list

      // test insert
      for(int i = 0; i < 9; i++) {
            cout << " Inserting " << i << " at position " << i/2 << endl;
            intList.insert(i, i/2); // insert i at position i/2

            // test output
            cout << intList << endl;

      }

      cout << " List empty? " << (intList.empty() ? "Yes" : "No") << endl;

      cout << "\nTry to insert at position -1" << endl;
      intList.insert(0, -1);

      cout << "\nTry to insert at position 10" << endl;
      intList.insert(0, 10);

      // test erase
      int index;
      cout << endl;

      while(!intList.empty()) {

            cout << " Give an index of a list element to remove: ";
            cin >> index;
            intList.erase(index);
            cout << intList << endl;

      }
      cout << " List is empty. " << endl;

      cout << "\nInserting " << myCapacity << " integers\n";

      for(int i = 0; i < myCapacity; i++)
            intList.insert(i, i);

      cout << " Attempting to insert one more integer: \n";
      intList.insert(-1, 0);

}

****************
0
edelossantos
Asked:
edelossantos
  • 3
3 Solutions
 
rstaveleyCommented:
I see a load of array stuff and then a load of linked list stuff. If you can purge every thing that has a '[' or a ']', you'll have something that is closer to a linked list than an array. Is this an academic exercise, mastering linked lists, or can you use the standard library instead?
0
 
rstaveleyCommented:
Also, it is hard to see any justification for new(nothrow). If it runs out of memory, let it throw.
0
 
rstaveleyCommented:
I  see you want your container to support random access:

          cout << " Inserting " << i << " at position " << i/2 << endl;
          intList.insert(i, i/2); // insert i at position i/2

Random access is conventionally done using operator[]().

You'd be better off using a vector or deque than a list, because linked lists are not designed to support random access. They are great for adding to the head or tail or splicing when you have already found an insertion point, but elements are not laid our sequentially in memory when you have linked lists, which means that random access isn't effcient and therefore is generally not supported by libraries. If you want to insert at position n, you need to get the head and walk through n nodes. A linked list implementation which supports operator[]() for random access is hiding this hard work and probably not doing you a favour, because you may be using the wrong container, if that's what you need.

Consider your requirements. If your teacher has asked you to implement random access in your container, she is asking you to do something that is unnatural for a linked list. Insertion in a linked list requires that you walk through the links from the head or tail node and insert a new link between that link and the link previous to it. The container itself should provide you the means to walk through the nodes and the means to insert a node when you have an iterator which tells it where to insert, but it shouldn't give you random access because that's something that a different container is better suited to.

The standard library gives you a good precedent. See the insert function at http://www.sgi.com/tech/stl/List.html. You would need to get the iterator by taking the begin() iterator (the list head) and then increment the interator i/2 times to get an iterator corresponding to the element before which the insertion is expected to take place. The insert for std::vector looks no better, but you know that elements are sequential in a vector and you can find the nth iterator in vector v using a constant time (i.e. quick) call &v[n]. Be warned that the insertion itself is slower than a list, because inserts need to move data, but getting the insertion point is faster.

What do you need your container to do?
0
 
jkrCommented:
Honestly, that piece of code is an odd mixture of a linked list and arrays together with code that uses quite mysterios variables that are never declared and so on. I'd rather start out from scratch than fixing this. I've added comments to indicate what I changed, but you will see a lot like

/* Just one comment: WTF is that supposed to do in a linked list?

*/

And it means just what it says. Anyway, the following compiles:

// list.h

#ifndef LIST_H
#define LIST_H

#include <iostream>
#include <fstream>

using namespace std;

//const int CAPACITY = 1024;
typedef int ElementType;

class Node; // fwd. decl. needed here

class List {

     // prototype for ouput operator
friend     ostream &operator << (ostream &out, const List &alist);  // needs to be a friend

public:

     List(int maxSize = 1024);
     ~List();
     // copy constuctor
     List(const List &origList); // no ',' here!
     // assignment operator
     const List &operator = (const List &rightHandSide);
     // list traversal
     void listTraversalNode();
     void printInReverse(Node *Head);   // call function to print list in reverse
     void bubbleSort(int); // boolean function ascending
     // empty operation
     bool empty() const;
     // insert and erase
     void insert(ElementType item, int pos);
     void erase(int pos);
     // output
     void display(ostream &out) const;

private:

     int mySize; // current size of list store in myArray
     //ElementType myArray[CAPACITY]; // array to store list of elements
     int myCapacity; // capacity of array
     Node *myArray; // pointer to dynamic array
     
};

class Node {

public:

     ElementType data;
     Node *next;

     Node* get_first() const { return first;} // private!
private:

     Node* first; // can't use 'NodePointer' here, since it isn't known yet
     int mySize;

};

typedef Node *NodePointer;

#endif

****************

// list.cpp

#include <cassert>
#include <iostream>
#include <fstream>
#include <list>
#include <new>
#include <string>
#include "node.h"

using namespace std;

// prototype for ouput operator
ostream &operator << (ostream &out, const List &alist);

// definition of class constructor
List::List(int maxSize) : mySize(0), myCapacity(maxSize) {

     //myArray = new ElementType[maxSize]; THIS IS A LIST OR AN INT ARRAY?????
     myArray = new Node;
     assert(myArray != 0);

}

// definition of class destructor
List::~List() {

     delete [] myArray;

}

// definition of copy constructor
List::List(const List &origList) : mySize(origList.mySize), myCapacity(origList.myCapacity) {

     // get new array for copy
     //myArray = new(nothrow) ElementType[myCapacity]; THIS IS A LIST OR AN INT ARRAY?????
     myArray = new Node;

/* Just one comment: WTF is that supposed to do in a linked list?

     if(myArray != 0) // check if memory available

          // copy origList's elements into this new array
          for(int i = 0; i < mySize; i++)
               myArray[i] = origList.myArray[i];
     else {
          cerr << " Inedaguate memory to allocate storage  for list. \n";
          exit(1);

     }
*/
}

// definition of assignment operator
const List &List::operator = (const List &rightHandSide) {

     // check that not self-assignment
     if(this != &rightHandSide) {
          // allocate new array if necessary
          if(myCapacity != rightHandSide.myCapacity) {
               delete [] myArray;
               myCapacity = rightHandSide.myCapacity;
               //myArray = new(nothrow) ElementType[myCapacity]; THIS IS A LIST OR AN INT ARRAY?????
               myArray = new Node;
               // check if memory available
               if(myArray == 0) {
                    cerr << " Inadequate memory to allocate stack. \n";
                    exit(1);

               }

          }
          // copy rightHandSide's list elements into this new array
          mySize = rightHandSide.mySize;

/* Just one comment: WTF is that supposed to do in a linked list?
          for(int i = 0; i < mySize; i++)
               myArray[i] = rightHandSide.myArray[i];
*/

     }
     return *this;

}
               
// definition of empty
bool List::empty() const {

     return mySize == 0;

}

// definition of display
void List::display(ostream &out) const { // you declared it as 'const', so use it!

/* Just one comment: WTF is that supposed to do in a linked list?
     for(int i = 0; i < mySize; i++)
          out << myArray[i] << " ";
*/

}

// definition of output operator
ostream &operator << (ostream &out, const List &aList) {

     aList.display(out);
     return out;

}

// definition of insert
void List::insert(ElementType item, int pos) {

     if(mySize == myCapacity) {
          cerr << " No space for linked list element, terminating execution. \n";
          exit(1);

     }
     if(pos < 0 || pos > mySize) {
          cerr << " Illegal location to insert -- " << pos << ". Linked list unchanged. \n";
          return;

     }

     // first shift array elements right to make room for item
     for(int i = mySize; i > pos; i--)
          myArray[i] = myArray[i - 1];

     // now insert item at postion pos and increase list size
/* Just one comment: WTF is that supposed to do in a linked list?
     myArray[pos] = item;
*/
     mySize++;

}

void List::listTraversalNode() {

     NodePointer ptr = myArray->get_first(); // need to declare it with a type!
     NodePointer first = ptr;

     while(ptr != 0) {
          ptr = ptr -> next; // appropriate statements to process ptr -> data

     }

     // where does 'dataVal' come from? Out of the blue????
//     NodePointer newptr = new Node(dataVal); // newptr of type NodePointer
     NodePointer newptr = new Node; // newptr of type NodePointer

     // where does 'predptr' come from? Out of the blue????
     NodePointer predptr = NULL;
     if(predptr != 0) { // not inserting at front
          newptr -> next = predptr -> next;
          predptr -> next = newptr;

     }
     else { // inserting at front
          newptr -> next = first;
          first = newptr; // reset first

     }

     if(predptr != 0) { // not deleting first node
          ptr = predptr -> next;
          predptr -> next = ptr -> next; // bypass

     }
     else { // deleting first node
          ptr = first;
          first = ptr -> next; // reset first

     }
     delete ptr; // return node to heap

}

// reverse print of list
void List::printInReverse(Node *Head) { // not sure on this one, need checked

       if (Head == 0){
       cout << "List is empty." << endl;
      }
     //int count = 0;
     Node *printPtr = new Node;
      printPtr = Head;

      while(printPtr != 0) {
       
     // cout << printPtr -> key << endl; "key is not a member of Node'"
     printPtr = printPtr->next; //advance pointer to next location in list...
       
      }
 
}

// boolean value function ascending ???
void List::bubbleSort(int nList) {

/* Just one comment: WTF is that supposed to do in a linked list?
     for(int i = mySize - 1; i > 0; --i) {
      for(int j =0; x < i; ++j) {
         if(nList[j] > nList[j + 1])
            swap(&nList[j],&nList[j + 1]);
      }
   }
*/
}  

// definition of erase
void List::erase(int pos) {

     if(mySize == 0) {
          cerr << " List is empty \n";
          return;

     }
     if(pos < 0 || pos >= mySize) {
          cerr << " Illegal location to delete -- " << pos << ". List unchanged. \n";
          return;

     }

/* Just one comment: WTF is that supposed to do in a linked list?
     // shift array elements left to close the gap
     for(int i = pos; i < mySize; i++)
          myArray[i] = myArray[i + 1];
*/
     // decrease list size
     mySize--;

}

int main() {

     int myCapacity = 42; // It is always a good idea to *declare* the variables you are using

     // test the class constructor
     List intList;
     cout << " Constructing intList\n";

     // test empty and output of empty list
     if(intList.empty())
          cout << " Empty: \n" << intList << endl; // test output of empty list

     // test insert
     for(int i = 0; i < 9; i++) {
          cout << " Inserting " << i << " at position " << i/2 << endl;
          intList.insert(i, i/2); // insert i at position i/2

          // test output
          cout << intList << endl;

     }

     cout << " List empty? " << (intList.empty() ? "Yes" : "No") << endl;

     cout << "\nTry to insert at position -1" << endl;
     intList.insert(0, -1);

     cout << "\nTry to insert at position 10" << endl;
     intList.insert(0, 10);

     // test erase
     int index;
     cout << endl;

     while(!intList.empty()) {

          cout << " Give an index of a list element to remove: ";
          cin >> index;
          intList.erase(index);
          cout << intList << endl;

     }
     cout << " List is empty. " << endl;

     cout << "\nInserting " << myCapacity << " integers\n";

     for(int j = 0; j < myCapacity; j++)
          intList.insert(j, j);

     cout << " Attempting to insert one more integer: \n";
     intList.insert(-1, 0);

}
0
 
edelossantosAuthor Commented:
You are too cool jkr, thank you very much.  I got the lab and the homework intertwined, hence, the absurd code.  

And thanks to you rstaveley.  Del
0

Featured Post

Free Tool: SSL Checker

Scans your site and returns information about your SSL implementation and certificate. Helpful for debugging and validating your SSL configuration.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

  • 3
Tackle projects and never again get stuck behind a technical roadblock.
Join Now