Thread: My first linked list

Well finally its done, my first linked list. This particular one is a doubly linked list. I want to have a 3d linked list (has nodes in front behind, top, bottom, left and right) but this is a good start

I've come across a few errors but it should run fine now, if it doesn't run fine tell me exactly what went wrong and where it went wrong (every function tells you what function you are in, originally to help me debug)

Right now you can only insert numbers into the linked list, however I'm going to create templated classes when I get around to it.

EDIT: and yes it screws up when you don't enter numbers, im not going to bother to fix that

well it is good.. But how about a better interface.. Like menu driven.... 1) Insert 2) Delete 3)Search 4) Sort etc etc.. Well serves no point but better to review by other users... Just a thought

Kinda hard to tell without the source, but I do see some odd things -- it says "doubly linked list constructor" everytime you add a value. Does this mean that you are reconstructing the entire list with every single new node or should that be "doubly linked list node constructor?" Also, it says "head" "tail" construction at the beginning -- does this mean that you are making head and tail nodes before any data is put into the list? That shouldn't be necissary. Also, it lists a node before the first and a node after the last as having "0" as a value when in actuality a node, and therefore a value, should not even exist there.

Originally posted by Shadow12345
doubly linked list constructor = node of doubly linked list constructor

list creates head, head creates tail

head and tail just return 0 because i don't care

So do we..

So do we

what is that supposed to mean? The reason I don't care is because that application isn't made to be presented in the sense that it's not going to go into my teacher at school and get graded, the little things like the head and tail's returning 0 should be changed but because this app is just a learning thing it isn't necessarily the most important thing. When you come right down to it I just wanted to get a working version of a linked list, the rest of the stuff is just superficial imo.

EDIT: i guess you thought i was being rude, saying 'i don't care' the way i did can be taken as rudeness but that wasn't my intent I swear, just image I said it as pasively as possible

From your implementation, I was questioning questioning why you construct head and tail nodes at the construction time of the list. In reality there should be no head or tail node when there is nothing in the list. If there is one value in the list then the node it is stored in is both the head and the tail, etc. Head and tail nodes should contain data like any other nodes.

That is a very strange piece of code for a double linked list. A good start to make a double linked list might be to look over some stl implementations. I would suggest this sort of structure...

Code:

template<typename T>
  class List
   {
       public:
            // usual list functions
            class Iterator
               { 
                   public:
                       // usual iterator funcs
                   private:
                       Node* currentnode;
                };
            class Const_Iterator
                {
                    public:
                       // usual iterator funcs
                   private:
                       Node* currentnode;
                };
      private:
             struct Node   // i like struct here cos its only POD(plain old data)but feel free to prefer class
               {
                    T Data;
                    Node* next;
                    Node* prev;
                };
              Node* Head;
              Node* Tail;
};

As others have said there is no point in not storing data in head and tail nodes. Head and tail pointers will change as the list gets nodes inserted but thats what linked lists are designed to do.

Originally posted by Shadow12345
again i reference to my books, they say not to store values in head or tail nodes, that they are just there to control the boundaries of the list.

Your books give a pretty odd and inefficient way of making a list then. A tail node and a head node are usable nodes -- there's no reason for them to be otherwise. Head just means that it has no node before it and tail just means there's no node after it.

EDIT: After looking at the source -- Inheritance and polymorphism on nodes will just force you to need a vtable pointer on every single node and also makes the program a lot more complex than it needs to be -- having all nodes as the same datatype is a more efficient approach -- just set the previous node pointer to 0 when there isn't one and the next node pointer to 0 when there isn't one.

Yeah -- I recommend dropping the whole "boundry node" business. You'll be better off. Also, a datastructure made of nodes with 6 branches in most cases will not be called a "linked list" because it's not really a "list." It'd be more of a web.

Have a look a this.Especially the exception safety stuff and class design stuff.

This makes interesting reading also

When you have read thru those you will probably have a better idea about how to design a linked list class.