Thread: Using a doubly-linked list to create a deque class.

  1. #1
    Registered User
    Join Date
    Nov 2005
    Posts
    7

    Using a doubly-linked list to create a deque class.

    I have to write a deque class using a doubly-linked list. I'm trying to add a node with a value into the list and this is the code I have for the insert that I have currently.
    Code:
       Node *prev = Head->Succ;
       newptr = new (nothrow) Node;
       
       newptr->Item = Item;
       newptr->pred = prev;
       newptr->succ = prev->Next;
    
       prev->succ->pred = newptr;
       prev->next = newptr;
    Also, my constructor looks like this...
    Code:
    template <typename EType>
    Deque<EType>::Deque(){
       Num = 0;
       Head = new (nothrow) Node;
       Tail = new (nothrow) Node;
    
       Head->Succ = NULL;
       Head->Pred = NULL;
    
       Tail->Succ = NULL;
       Tail->Pred = NULL;
    };

    My destructor doesn't have anything too it right now. When I compile, I get 3 unresolved external errors, one regarding the constructor, one the destructor, and one the function called put_front which is the section I am asking about and I'm not really sure why. My driver file I'm using to test this looks like this...
    Code:
    int main(){
       bool flag;
       int Item;
       Deque<int> A;
       
       Item = 10;
       flag = A.put_front(Item);
       cout << flag << endl;
       return 0;
    }
    First of all, this list uses a dummy node. So, I believe this will work if there are already some nodes containing values stored in the list after the dummy node, however I am not sure how to implement something like this in an empty list. I'm still really shaky with whats going on with these lists so any explanation would be great.

  2. #2

  3. #3
    Registered User
    Join Date
    Apr 2003
    Posts
    2,663
    1) If you don't understand linked lists, don't complicate it with templates. Write a linked list for ints and when you get that program working, then convert it to a template, which is simple enough: replace int with T everywhere you want the type to be a variable.

    2) To understand linked lists, you have to draw pictures. Prelude created some inspired ascii art which you might want to check out:

    http://faq.cprogramming.com/cgi-bin/...&id=1073086407

    To trouble shoot your code, go through the execution line by line drawing your own pictures and put the variable names in columns and cross out the old value and write down the new value when the code changes a variable.
    Last edited by 7stud; 11-14-2005 at 12:38 AM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Screwy Linker Error - VC2005
    By Tonto in forum C++ Programming
    Replies: 5
    Last Post: 06-19-2007, 02:39 PM
  2. circular doubly linked list help
    By gunnerz in forum C++ Programming
    Replies: 5
    Last Post: 04-28-2007, 08:38 PM
  3. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  4. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  5. doubly linked list problem
    By YevGenius in forum C Programming
    Replies: 4
    Last Post: 05-02-2004, 08:54 PM