3 replies to this topic

[bbto]

Hi, i'm currently working on a assignment programmer with need to implement an array based linked list that not using pointer.
need to look like this
 A1..jpg   63.57K   168 downloads
linked list in simple, but an array based linked list is kind of new to me.
i have u version of code that i wrote. i dun know which one is right structure.

this is only past of the code not all, only show the structure.
1.

struct Node{
    char item;
    int next;
};

class AryList{
    public:
              
    private:

        Node ary[MAX_SIZE];//array based linked list

}

2.

struct Node{
    char item;
    int next;
}Node_array[MAX_SIZE];

which one is the correct one for array based linked list?
thank you!

[Flying Dutchman]

The next element has to be pointer, like so

struct Node {
    char item;
    Node* next;
};

And as far as I know, you have to create each element in array manually (new and delete operators in C++ or malloc and free in C).

#include <iostream>

using namespace std;

static int bytes = 0;

struct Node {
  Node() { bytes += sizeof(char); }
  ~Node() { bytes -= sizeof(char); }
  char item;
  Node* next;
};

int main() {

  Node* head = new Node;
  Node* curr = new Node;
  head = curr;                  // save position of first element, so we know where our list starts
  
  const int total = 5;
  char c = 'A';
  
  for (int i = 0; i < total; ++i, ++c) {
    curr->item = c;             // assign value
    curr->next = new Node;      // create new element
    curr = curr->next;          // move to that new element
  }
  curr->next = NULL;            // place a 'stop' sign

  curr = head;                  // move to first element
  for (int i = 0; i < total; ++i) {
    cout << curr->item << " ";  // display element
    curr = curr->next;          // move to next one
  }
  
  for (int i = total; i > 0; i--) {
    curr = head;                // get position of first element
    for (int j = 0; j < i; j++) {
      curr = curr->next;        // move to the last element
    }
    delete curr;                // delete last element
  }
  delete head;
  delete curr;

  cout << "Bytes: " << bytes;
  return 0;
}

I know cleanup is cheap and dirty... but it works :)

[bbto]

Flying Dutchman said:

The next element has to be pointer, like so

struct Node {
    char item;
    Node* next;
};

thanks for reply.
but the thing is ...the requirement is not to use pointer.
the next is a integer that contain the index of next item.

[julmuri]

I wold use the second method. ie:

template < class T >
class Node
{
public:
    Node()
        : data( 0 ), next( 0 )
    { }
    Node( const T& _data, int _next )
        : data( new T( _data )), next( _next )
    { }
    Node( const Node& other )
        : data( new T( other.data )), next( other.next )
    { }
    Node& operator=( const Node& other )
    {
        if ( this != &other )
        {
            T* temp = data;

            if ( 0 != other.data )
                data = new T( *other.data );
            else
                data = 0;

            if ( 0 != temp )
                delete temp;

            next = other.next;
        } // if

        return *this;
    }
    ~Node()
    { if ( 0 != data ) delete data; }

    T& GetData()
    { return *data; }

    int GetNext() const
    { return next; }

private:
    T*    data; // change to smart ptr
    int next;

};

template < class T, std::size_t S = 128 >
class ArrayList
{
public:
    ArrayList()
    { }
    ArrayList( const ArrayList<T>& other )
    { this->Copy( other ); }
    ArrayList& operator=( const ArrayList<T>& other )
    {
        if ( this != &other )
            this->Copy( other );

        return *this;
    }
    ~ArrayList()
    { this->Clear(); }

    bool Add( const T& data )
    {
        // insert data at the end of the list
        // ...
    }

    void Remove( const T& data )
    {
        // find and remove from the list
        // ...
    }

    void Clear()
    {
        // clear the list
        // ...
    }

    bool GetFirst( Node<T>& first )
    {
        if ( 0 == size )
            return false;

        first = nodes[0];
        return true;
    }

    bool GetNext( const Node<T>& node, Node<T>& next )
    {
        if ( node.GetNext() >= size )
            return false;

        next = nodes[node.GetNext()];
        return true;
    }


private:
    void Copy( const ArrayList<T>& other )
    {
        Node<T> node;

        this->Clear();
        for ( bool result = other.GetFirst( node ); result; result = other.GetNext( node, node ))
            this->Add( node.GetData() );
    }

private:
    std::size_t    size;
    Node<T>        nodes[S];

};

( Yes, Iam very bored. )