Thread: Prepend Double linked list

  1. #1
    Registered User dalek's Avatar
    Join Date
    May 2003
    Posts
    135

    Prepend Double linked list

    Hi - more linked lists issues

    I am working on a simple prepend function for a doubly linked list - but I have hit a snag. Many of the examples I have seen use a similar algorithm to what I am using here, but I don't understand how to get around the problem when pointing the old head of the list to the new node. I am getting a memory violation issue on that line...
    Code:
    #include <iostream>
    
    using namespace std;
    
    typedef struct Node
    {
    	int *data;
    	Node *next;
    	Node *prev;
    } NODE;
    
    // Function prototypes
    void output_fwd(void);
    void insert_beg(int *data);
    
    // The list
    NODE *head;
    NODE *tail;
    
    int main(void)
    {
    	int num;
    	
    	cout << "Enter a number: ";
    	cin >> num;
    
    	while (num != 999)
    	{
    		insert_beg(&num);
    		cout << "Enter a number: ";
    		cin >> num;
    	}
    	
    	output_fwd();
    
    	return 0;
    }
    
    void output_fwd(void)
    {
    	NODE *current;
    
    	current = head;
    
    	while (current != NULL)
    	{
    		cout << "Number: " << *current->data << endl;
    		current = current->next;
    	}
    }
    
    void insert_beg(int *data)
    {
    	NODE *temp = new NODE;
    	temp->data = new int;
    
    	*temp->data = *data;
    
    	temp->next = head;
    	temp->prev = NULL;
            // This is the problem line..
    	head->prev = temp;
    	head = temp;
    }

  2. #2
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    Always check for an empty list:
    Code:
    if (head)
        head->prev = temp;
    You were dereferencing a null pointer by saying head->prev on the first prepend. At that point head was null, so you got slapped in the face.
    p.s. What the alphabet would look like without q and r.

  3. #3
    Registered User dalek's Avatar
    Join Date
    May 2003
    Posts
    135
    Oh hell..

    Thanks a lot for your help Brighteyes! I feel a bit stupid when it comes to pointers for some reason.

  4. #4
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    >Oh hell..
    Would you like my double linked list library? That would save you a lot of work.

    [edit]It's in C though, for C++ the std::list would be way better.[/edit]
    p.s. What the alphabet would look like without q and r.

  5. #5
    Disturbed Boy gustavosserra's Avatar
    Join Date
    Apr 2003
    Posts
    244

    just a question

    Originally posted by Brighteyes
    >Oh hell..
    Would you like my double linked list library? That would save you a lot of work.

    [edit]It's in C though, for C++ the std::list would be way better.[/edit]
    Does your linked list has a pointer to the last node? I always think about the overhead of having a pointer to the first and last nodes... and I think about the advantages like faster insertion at the end of the list, and other usefull things
    Just curious...
    Nothing more to tell about me...
    Happy day =)

  6. #6
    Registered User dalek's Avatar
    Join Date
    May 2003
    Posts
    135
    Would you like my double linked list library? That would save you a lot of work.
    Thanks, but thats OK. I know I am only covering ground that has been covered a bazillion times before. But I am trying to ram this into my head. I need to know it, I need to understand it!

  7. #7
    Open to suggestions Brighteyes's Avatar
    Join Date
    Mar 2003
    Posts
    204
    >Does your linked list has a pointer to the last node?
    Not built in, no. I decided against it for simplicity sake, though you can easily place an iterator to point at the end of the list if you need quick insertions there:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include "List.h"
    
    /* Error handling omitted in this example */
    Iterator newItem(int data)
    {
        Iterator item = malloc(sizeof (*item));
        item->data = malloc(sizeof (int));
    
        *(int*)item->data = data;
        item->prev = item->next = 0;
    
        return item;
    }
    
    int main(void)
    {
        List head = 0;
        Iterator tail;
        int i;
    
        for (i = 0; i < 10; i++)
            head = ListAddBack(ListLast(head), newItem(i));
    
        tail = ListLast(head);
        head = ListFirst(head);
    
        printf("First: %d\n", *(int*)ListContent(head));
        printf("Last: %d\n", *(int*)ListContent(tail));
    
        return 0;
    }
    It's a bit ugly with casting because of the void pointers. Try writing a generic library in C and you'll remember how much you love templates.
    p.s. What the alphabet would look like without q and r.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Unknown memory leak with linked lists...
    By RaDeuX in forum C Programming
    Replies: 6
    Last Post: 12-07-2008, 04:09 AM
  2. Replies: 6
    Last Post: 03-02-2005, 02:45 AM
  3. How can I traverse a huffman tree
    By carrja99 in forum C++ Programming
    Replies: 3
    Last Post: 04-28-2003, 05:46 PM
  4. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 06:40 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM