I need some help on my linked lists app

I'm messing around with linked lists, cause I've just learned (mostly :D ) how to use singly linked lists. I NEED to learn doubly linked ones sometimes soon. Anyway, I decided to go off and experiment, and see if I can do doubly linked lists. Well, I haven't totally implemented the doubly part FULLY yet, but I will. After I solve this. How do I get my p node (i.e. the thingy that traverses the list) to start at the beginning? I use MSVC6 on Win98. Here's the code:

Code:

---

#include <iostream.h>
#include <dos.h>
#include <conio.h>
#include <stdlib.h>

void New(int v);

class node {
 public:
  node(node *pre);
  int x;
  node *next;
  node *prev;
 private:
};

node::node(node *pre) {
 *prev = *pre;
}


void main() {
 unsigned long int n[2000];
 unsigned int l;
 int ch;
 n[0] = 0;
 n[1] = 1;
 l = 2;
 clrscr();
 cout << "This is a doubly linked list test.\nBy: Scott A. Hand\n";
 node *root(NULL);
 node *p(NULL);
 root->prev = NULL;
 do {
  clrscr();
  cout << flush << "Menu:\n[1] New\n[2] View All\n[3] Quit\n> ";
  cin >> ch;
  if (ch == 3) {
  clrscr();
  cout << "This program was made by: Scott A. Hand, goodbye.\nPress any key to quit...\n";
  getch();
  exit(0);
  }
  if (ch == 1) {
  root->next = new node(root);
  cout << "Enter value: ";
  cin >> root->x;
  root->next = NULL;
  }
  if (ch == 2) {
  p = NULL;
  p = root;
  do {
    cout << p->x << endl;
  } while (!p->next == NULL);
  getch();
  }
 } while (ch != 3);
}

---

Thanks in advance,
Scott

I suggest you get in the habit of creating a new node as a clear cut entity not associated with the list and then, once it's made find out where to put it in the list rather than always assigning the new node to root. In the new node assign NULL to newNode->prev in addition to assigning NULL to newNode->next.

If the list is empty, meaning root is NULL, then the new node is assigned to root. If root is not NULL, then you have to find where to put the new node based on whatever criteria you choose. To determine where it goes assign root to p. Then compare the value in p you are using for your criteria to the appropriate value in the new node. Move p one node to the right/down/whatever by assigning p->next to p until you find the appropriate spot in the list. Realign any pointers necessary to insert the node in the appropriate spot.

Well, first of all, your node creation should look like this:

node * root = new node(NULL);

If I were you, I'd make a linked list class, as well as a node class.

Something like this:

Code:

---

class LinkedList{
public:
        LinkedList();
        ~LinkedList();
        void AddNode(LinkedListNode);
        void DeleteNode(LinkedListNode *);
        LinkedLinstNode * GetCurrentNode();
        void Start(); //sets current to the first node
        void End(); //sets current to the last node
        bool IsValid(); //does current point to a valid node?
        void Next(); //current points to next node
        void Prev(); //current points to previous node
private:
        LinkedListNode * begin; // first node, or NULL if none exist
        LinkedListNode * end; //last node, or NULL if none exist
        LinkedListNode * current;
};

---

Then, it's easy to iterate through the list, as much as you want.

Code:

---


for (list.Start();list.IsValid();list.Next()){
        //do whatever for each node
}

---

Note that with this, you will need to always check IsValid() before using a node, as current is allowed to be null if you move off the end of the list. This is an effective way to do stop conditions. Every function that operates on current should check for NULL too.

As another note, you should make the LinkedListNode have a pointer to the LinkedList that it is a part of -- this is for error checking. It's nice and easy to delete a linked list node from a list, without scanning the list, simply by using the prev and next pointers -- but it should check to make sure the node is a member of that list.

So, this should not do anything:

(listA and listB are each LinkedList objects)

listA.DeleteNode(listB.GetCurrentNode());

So the deleteNode function should "know" that the node passed to it was from another linked list, not this one. Also, AddNode should add a copy of the node passed, so someone couldn't pass a node that was already in the list and cause a loop or a break in the list -- a new node should be built internally, and the data copied from the node passed in, which should be unchanged.