My first linked list

This is a discussion on My first linked list within the C++ Programming forums, part of the General Programming Boards category; Well finally its done, my first linked list. This particular one is a doubly linked list. I want to have ...

  1. #1
    Shadow12345
    Guest

    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
    Attached Files Attached Files
    Last edited by Shadow12345; 12-28-2002 at 01:02 PM.

  2. #2
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    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

  3. #3
    Shadow12345
    Guest
    because the only purpose of the program is to get a working linked list, i dont' care about how it looks because it's just going to be saved somewhere and never looked at again.

  4. #4
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    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.

  5. #5
    Shadow12345
    Guest
    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

  6. #6
    Its not rocket science vasanth's Avatar
    Join Date
    Jan 2002
    Posts
    1,683
    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..

  7. #7
    Shadow12345
    Guest
    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
    Last edited by Shadow12345; 12-30-2002 at 08:33 AM.

  8. #8
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    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.

  9. #9
    Shadow12345
    Guest
    Well I don't know. This isn't really 'my' implementation, I took notes from two different C++ books I have and built the application from my notes. Both books use head and tail nodes to control the boundaries of the list.

    In reality there should be no head or tail node when there is nothing in the list
    Well in reality there isn't anything in the list when there are just head and tail nodes. Head and tail nodes aren't supposed to have any value (despite the fact that I used 0 which is a value instead of null which specifically means no value).

    Head and tail nodes should contain data like any other nodes.
    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.

    I attached my source so you can look at it if you want. Feel free to change it, make more suggestions, etc
    Attached Files Attached Files

  10. #10
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    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.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  11. #11
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    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.
    Last edited by Polymorphic OOP; 12-30-2002 at 09:57 AM.

  12. #12
    Shadow12345
    Guest
    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.
    Well I guess that's a fair argument, I mean you would expect an entire list to be used to store data, in that case it is somewhat inefficient but is almost a moot point because of how much memory computers today have. I don't see what is wrong with my setup, when you get right down to it it is still a functioning linked list that can accept data and puts it in the appropriate place. I am not concerned with being 'right' or 'wrong' I just want to know why mine is bad so I don't run into problems in the future. I've started writing a linked where each internal node points to 6 different nodes and now I am trying to decide whether or not to use 'boundary' nodes such as the head and tail nodes being described.

  13. #13
    Programming Sex-God Polymorphic OOP's Avatar
    Join Date
    Nov 2002
    Posts
    1,078
    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.

  14. #14
    Skunkmeister Stoned_Coder's Avatar
    Join Date
    Aug 2001
    Posts
    2,572
    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.
    Free the weed!! Class B to class C is not good enough!!
    And the FAQ is here :- http://faq.cprogramming.com/cgi-bin/smartfaq.cgi

  15. #15
    Shadow12345
    Guest
    I guess I will drop the 'boundary node business' seeing as it seems to be unpopular.


    A good start to make a double linked list might be to look over some stl implementations
    where might I find some stl implementations?

    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.
    *bites knuckle*

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. C++ Linked list program need help !!!
    By dcoll025 in forum C++ Programming
    Replies: 1
    Last Post: 04-20-2009, 10:03 AM
  2. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  3. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21