   Deleteing the head of a linked list??
  Hey, ive been trying to make a Node class that i can use to make linked lists out of objects with. However when coding my delete function I realised I might end up with a problem if i delete the head node of my list when there are other nodes attached to it, (ie. if in the program code im accessing the list via its head, and then delete the head i will loose all access to the other nodes in my list). Is there a way around this? I was thiking maybe passing a pointer to the head of the new list at the end of the delete function every time a node is deleted but that seems a bit nasty =S or am i just approaching this completely wrong?PS. I havent compiled the code as when i realised this problem i figured it was best to just stop till i figuered it out so there might be other errors in it but im more concerned about this problem than those :)#ifndef __NODE_H#define __NODE_Hclass Node {protected:Node *next;Node *prev;public:Node() {next = NULL;prev = NULL;};~Node() {};addNode(Node *newNode) {if(next != NULL){next-&gt;addNode(Node *newNode);}else{next = newNode;newNode-&gt;setPrev(*this);}};Node getNext() { return next; };Node getPrev() { return prev; };void setPrev(Node *prevNode) { prev = prevNode; };void setNext(Node *nextNode) { next = nextNode; };// Deletes this node void deleteNode() { // If there is a node after and before this one, link them togetherif(next != NULL && prev != NULL){prev-&gt;setNext(next);next-&gt;setPrev(prev);}// If this is the last node in the list, // make the node before this the new end of the listelse if(prev != NULL && next == NULL){prev-&gt;setNext(NULL);}// If this is the head of the list make the next node the new headelse if(prev == NULL && next != NULL){next-&gt;setPrev(NULL);}delete(this);};};#endif;
  I'm a little tired, so if I misread, sorry!But anyway, the main problem for you lies in keeping track of the current head of the list. If you delete the head, then then the next one should take over - you'll have to check when deleting whether or not it's the head you're getting rid of. E.g:  Node *head;  void my_code_deleting_nodes(int node_num)  {    Node *temp_node;    if(node_num == 0)    { temp_node = head->getNext(); head->deleteNode();j head = temp_node;    }  }Note that above isn't really the greatest bit of code, doesn't do its job properly, but you should get the idea.Another thing (that looks c++ right?) you might want to look into making a templated linked list class. I spent some time making one, saves a lot of effort later on!   ;Quote:Original post by mirvyou might want to look into making a templated linked list class.Instead of looking into making them, look into using std::list (http://www.sgi.com/tech/stl/List.html) which is a linked list far more efficient than you could make it.   ;  hmm thing is that looks like id be having a linked list class which holds data about the list ie. its head etc. which is what I had before. However, what i want to do now is have a base node class which other objects can then extend so i can link them together if that makes sense, sure ive seen it done somewhere before cant remember where tho =S. I just thought it would be a bit nicer than how i had it before, but I might just not bother lol   ;  There are three basic options. I've listed them in order from worst to best:// Option 1: have each node tell you what to do// when you delete it from the linked listclass Node{public:   Node* RemoveThisNode()   { return this->Next;   }// etc.};Node* foo = bar();foo = foo->RemoveThisNode();if(!foo)  // end of the list!//Option 2: split the idea of a "linked list" from the idea of a "list node"// This is the most common implementation and the cleanest (usually)class LinkedList{public:   ListNode* GetHead() const   { return _Head;   }   void DeleteHead()   { if(_Head)    _Head = _Head->GetNext();   }   // etc.protected:   ListNode* _Head;};LinkedList list;InsertABunchOfNodesIntoList(list);list.DeleteHead();// Option 3: by far the best solution// (Unless you just want to learn how a linked list// class is implemented, and not really use it.)#include <list>std::list<NodeType> linkedlist;;You could create a certain "sentinel" object, which is always the head of the list. This way, the other objects in the list don't have to worry about the case of being the head of the list. Cheers   ;  Here's my solution, it's short, and will crash horribly when used wrong.#include <iostream>using namespace std;class Node{ public:  Node* next;  Node* prev;  Node() { glue(this); };  ~Node() {};  void glue(Node* toThis) { next = toThis; next->prev = this; };  void deleteNode() { prev->glue(next); delete this; };  void add(Node* n) { prev->glue(n); n->glue(this); };  bool isEmpty() { return next == this; };};int main(int argc, char *argv[]){  // Create a list  Node* list = new Node();  // Add 2 nodes  list->add(new Node());  list->add(new Node());  // Traverse list and output addresses  for (Node* i = list->next; i != list; i = i->next) cout << i << endl;  // Delete nodes  while (!list->isEmpty()) list->next->deleteNode();  // Delete the list  delete list;  // Done  system("PAUSE");} [Edited by - Wiggin on June 3, 2006 11:30:59 AM]