Thread: Doubly Linked List Problem

  1. #1
    Registered User
    Join Date
    Oct 2011
    Posts
    1

    Doubly Linked List Problem

    I'm working with a doubly linked list, writing a bunch of functions to do basic alterations to the list, but my functions for adding a node after an existing node isn't working, and my function for deleting a node at the head of the list isn't working either. Here's my code for these functions:
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    
    
    typedef int Info;
    typedef struct {
        Info info;
    } Item;
    typedef Item* ItemRef;
    
    
    typedef struct NodeStruct* NodeRef;
    typedef struct NodeStruct {
        ItemRef item;
        NodeRef next;
        NodeRef prev;
    } Node;
    
    
    typedef struct {
        NodeRef head;
        NodeRef tail;
        int size;
    } Dlist;
    typedef Dlist* DlistRef;
    
    void insertNodeAt(DlistRef dl, Info oldval, Info newval){
    /* insert a new node with value newval after the node with value oldval */
    /* if oldval is not found in the list, insert newval at the end of the list */
    /* use findNode() to implement this function */
        NodeRef x = findNode(dl, oldval);
        NodeRef y;
        NodeRef z = initializeNode(newval);
        if(x != NULL){
            if(x->next != NULL){
                x->next = y;
                z->next = x->next;
                z->prev = x;
                y->prev = z;
                x->next = z;
            }
            if(x->next == NULL){
                z->next = NULL;
                z->prev = dl->tail;
                x->next = z;
                dl->tail = z;
            }
        }
        if(x == NULL){
            insertNodeAtTail(dl,newval);
        }
        dl->size++;
    }
    
    bool deleteNodeAtHead(DlistRef dl, Info* g){
    /* delete new node at the beginning of the list */
    /* return false if list is empty and true otherwise */
    /* return value of deleted item in g */
        NodeRef y = dl->head;
        NodeRef z = y->next;
        if(y==NULL){
            return false;
        }
        if(y!=NULL){
            dl->head = z;
            z->prev = NULL;
            y->next = NULL;
            *g = y->item->info;
            deallocateNode(y);
            dl->size -= 1;
            return true;
        }
    }
    Any ideas why these aren't working?

  2. #2
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    How do you know that they are not working?
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  3. #3
    Registered User
    Join Date
    Nov 2009
    Location
    Maryland, USA
    Posts
    46
    Quote Originally Posted by engrstudent View Post
    Code:
                x->next = y;          /* Useless--overwritten below */
                z->next = x->next;
                z->prev = x;
                y->prev = z;           /* y is an uninitialized pointer */
                x->next = z;
    I didn't analyze very much of it, but using an uninitialized pointer is always asking for trouble.

    It helps to draw pointer problems out with boxes and arrows.

    I also find that double indirection (pointers to pointers) actually reduces complexity a little by eliminating the need for some intermediate variables.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. doubly linked list
    By bahareh in forum C++ Programming
    Replies: 7
    Last Post: 03-28-2007, 01:31 PM
  2. doubly sorted linked list problem
    By f6ff in forum C++ Programming
    Replies: 3
    Last Post: 04-04-2006, 10:57 AM
  3. Doubly-Linked List
    By jgs in forum C Programming
    Replies: 7
    Last Post: 04-18-2005, 01:39 PM
  4. singly linked list to doubly linked list
    By t48j in forum C Programming
    Replies: 3
    Last Post: 03-23-2005, 06:37 PM
  5. doubly linked list problem
    By YevGenius in forum C Programming
    Replies: 4
    Last Post: 05-02-2004, 08:54 PM

Tags for this Thread