Thread: Can someone explain Linked List to me?

  1. #16
    Registered User
    Join Date
    Dec 2005
    Posts
    15
    hmm the simplest way to destroy a whole list is to write a function that eliminates one element the list and use that in another function which has a while or for ...
    something like
    Code:
     #include <iostream.h>
    #include <conio.h>
    struct elem{int info;
                        elem *next;
                      };//this is a simple linked list ...there's no need for decalarting a double one you ll just complicate matters
    elem *f;//see that you only need the first element of the list :D
    ///considering you've already created the list :)
    void eliminate(elem *&n){
            elem *r; r=n->next; n->next=n->next->next; delete r; //i've just deleted n->next :D 
             
    }
    
    void main(){
    for(elem *q=f;q->next;q=q->next)
         eliminate(q);//with the little trick i used deleteing q->next i never got to deleting p
         delete p;//so here i delete p :)
    }
    there you have it
    so there is no need for a double linked list

  2. #17
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    That is simple?

    Aside from being extremely complicated, it's also incorrect, because it only deletes every second element.

    And then there's that nonsense about not needing double-linked lists. Sure, there are situations where single-linked suffice, but in general, you'll discover many, many use cases where single-linked lists are bad. (For example, you cannot eliminate an arbitrary element from a list given just the list container and the node to delete in constant time as you can do with dll. You need linear time for that. You cannot iterate from back to front. There are others.)
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  3. #18
    Registered User
    Join Date
    Dec 2005
    Posts
    15
    haha yeah i only delete half +1 of the list ...sorry didn't really compile that *ahem* anyways who wants to delete a whole list anyway !?!?? you can delete the first element and never hear from that part of the momory ever again ...lost ...in the unknown ) ... right. :|



    *coughs, and is gone*

  4. #19
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49
    I need to, I don't need a whole lot of junk data eating up RAM, I need to reuse the RAM for something else.

  5. #20
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    Well, I think your last code to delete the list was right. Just set all remaining pointers to NULL afterwards.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  6. #21
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49

    Talking

    Thanks, I can remove the extra delete head and delete tail now. Say, I wanted to create a list like the stl_list, but I don't want to blantly copy them. So would this work?
    Code:
    struct Node {
      template<typename T>
      struct NodeData {
        T data;
        NodeData(T element) { data = element; }
      };
      Node* prev;
      Node* next;
      NodeData data;
    };
    I wanted to compose a template inside a normal struct or class, can this work? I haven't tried yet cause I need to figure some way to seperate normal types from template types.

    I like the stl design because they can hide their implementation.

  7. #22
    Cat without Hat CornedBee's Avatar
    Join Date
    Apr 2003
    Posts
    8,895
    No, it can't work. You need to supply NodeData a template parameter on instantiation (where you declared the data member of Node), which means you need that parameter in Node too.
    There is a way of storing arbitrary data in a non-template, but it involves quite a bit of runtime overhead, and thus is not really suitable for generic containers.

    Which STL hides its implementation? I've yet to see one.
    All the buzzt!
    CornedBee

    "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code."
    - Flon's Law

  8. #23
    C++ Newbie
    Join Date
    Nov 2005
    Posts
    49
    I can't find their function and type implementations, does that mean I have to search through every single header file? Example been the _List_node_base structure.

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. Replies: 5
    Last Post: 11-04-2006, 06:39 PM
  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, 09:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM