Implementing a linked list, some problems

This is a discussion on Implementing a linked list, some problems within the C++ Programming forums, part of the General Programming Boards category; Ok, I am implementing a basic linked list, in the form of a stack, and for my push function I ...

  1. #1
    'AlHamdulillah
    Join Date
    Feb 2003
    Posts
    790

    Implementing a linked list, some problems

    Ok, I am implementing a basic linked list, in the form of a stack, and for my push function I have:

    Code:
    void Push(Node** head, int data)
    {
    
    Node* new_node = new Node;
    new_node->data = data;
    new_node->next = *head;
    *head = new_node;
    }
    now, this works fine, displaying its data works perfectly. However, it is very.... un-modular to future development. When I try to do this:
    Code:
    void Push(Node** head, Node* new_node)
    {
    new_node->next = *head;
    *head = new_node;
    };
    displaying it using the standard while(Current->next != NULL) loop, it goes into an infinite loop, only displaying the last pushed number.

    I was wondering what I am doing wrong, cause linked lists are pretty basic things, and I had them working perfectly before, but during this semester of college, my main focus was making sure I got a 4.0 GPA and so I forgot the proper way to do linked lists.

  2. #2
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,676
    What you've shown so far looks ok. You'll have to post more code.

    gg

  3. #3
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    The problem is elsewhere, your code is fine (though use of references would save you from double pointer hell):
    Code:
    class Stack {
    public:
      Stack ( int init, Stack *link )
        : data ( init )
        , next ( link )
      {}
    public:
      int data;
      Stack *next;
    };
    
    void Push ( Stack *&top, Stack *new_item )
    {
      new_item->next = top;
      top = new_item;
    }
    
    void Pop ( Stack *&top, Stack *&old_item )
    {
      old_item = top;
      top = top->next;
    }
    
    #include <iostream>
    
    int main()
    {
      Stack *mystack = 0;
      Stack *save;
    
      for ( int i = 0; i < 10; i++ )
        Push ( mystack, new Stack ( i, mystack ) );
      while ( mystack != NULL ) {
        Pop ( mystack, save );
        std::cout<< save->data <<std::endl;
        delete save;
      }
    }
    My best code is written with the delete key.

  4. #4
    'AlHamdulillah
    Join Date
    Feb 2003
    Posts
    790
    from what you posted prelude, my problem is here:

    Code:
    ...
     
    while(Current->next != NULL)
    {
    ...
    }
    
    ...
    it should be :

    Code:
    while(Current != NULL)
    {
    ...
    }

    EDIT: hmmm.... that wasnt the problem.

    here is my code btw.

    Code:
    #include <stdio.h>
    #include <iostream>
    using namespace std;
    
    struct node
    {
      int data;
      node *next;
    };
    
    void Push(node** head,node* new_node)
    {
      new_node->next = *head;
      *head = new_node;
    };
    
    void display(node* head)
    {
      node *current;
      current = head;
    
      while (current != NULL)
      {
    
        cout << current->data << endl;
        current = current->next;
      }
    };
    
    int main()
    {
      node* head = new node;
      node* item = new node;
    
      head->next= NULL;
    
      item->data = 5;
       Push(&head,item);
       item->data = 8;
       Push(&head,item);
    
    display(head);
      return 0;
    };
    Last edited by EvBladeRunnervE; 12-12-2003 at 07:44 AM.

  5. #5
    'AlHamdulillah
    Join Date
    Feb 2003
    Posts
    790
    also, a bit off topic prelude, but even though their are double-linked lists, with a prev and next pointer, I heard that there are actually quadruple linked lists, but I cannot imagine:

    1) how they are implemented
    2) what their purpose is.

    I was wondering if you had heard of them.

  6. #6
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,676
    >> 1) how they are implemented
    Add 4 pointers to your node object.

    >> 2) what their purpose is.
    Depends on what the 4 pointers are pointing to.
    One thing that comes to mind is a linked node implementation of a matrix or grid, where each node can traverse to it's immediate neighbor. If you imagine it in a two dimensional space, imagine traversing north, south, east, or west from a given node.

    gg

  7. #7
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    Remember that each new node is distinct from the others. What you were doing is using a single memory block (assigned to item) as all of the new nodes. The end result is some messed up links, but not a linked list. Try this instead:
    Code:
    void display(node* head)
    {
      node *current;
      current = head;
    
      while (current->next != NULL)
      {
        cout << current->data << endl;
        current = current->next;
      }
    };
    
    int main()
    {
      node* head = new node;
      node* item = new node;
    
      head->next= NULL;
    
      item->data = 5;
      Push(&head,item);
      item = new node;
      item->data = 8;
      Push(&head,item);
    
      display(head);
      return 0;
    };
    I changed your display function back to the way it was because you appear to want head as a dummy node instead of a valid data node. My changes are highlighted red.

    >I heard that there are actually quadruple linked lists
    You can have as many links as you want. I've written a data structure that has next, prev, up, down, in, and out to make up the linked equivalent of a three dimensional array.

    >I was wondering if you had heard of them.
    Unfortunately, I've had the bad luck of working with them. Avoid such structures whenever you can, they're a nightmare to maintain.
    My best code is written with the delete key.

  8. #8
    'AlHamdulillah
    Join Date
    Feb 2003
    Posts
    790
    works perfectly prelude. I was forgetting the fact that a pointer just points to a memory location, so when you have a pointer to a pointer in the case of a linked list, you need to allocate memory for new data.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. linked list problems (null values)
    By scwizzo in forum C++ Programming
    Replies: 2
    Last Post: 12-03-2008, 05:04 PM
  2. Duplicating value of pointer to linked list
    By zephyrcat in forum C Programming
    Replies: 14
    Last Post: 01-22-2008, 02:19 PM
  3. Adding directory/file names to a linked list
    By thoseion in forum C Programming
    Replies: 13
    Last Post: 12-08-2006, 12:13 PM
  4. Problem with linked list ADT and incomplete structure
    By prawntoast in forum C Programming
    Replies: 1
    Last Post: 04-30-2005, 01:29 AM
  5. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM

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