CODEWITHSUNDEEP
clistlinked-list
PnP
PnP

Reputation: 3185

How to implement "prev" pointer logic in doubly linked list

I need help with implementing the prev pointer logic part of a doubly linked list.

Basically, I'm in the middle of constructing a Linked List, which at the moment is singly linked. I have added the necessary struct node *prev; to my Struct, so that I can have both next pointers and previous pointers in each node within the list. But now I've hit a wall, and really don't know how to implement the *prev pointer within my code.

I'm not looking for exact solutions, really just a push in the right direction.

typedef struct L { 
    char val;
    struct L *next;
    struct L *prev;
} List;

List *insertList(char val, List *t1 );
List *createList(void);

int main(void) {
    List *z = createList();
    while ( z != NULL ) {
        printf("%c", z->val);
        z = z->next;
    }
    return 0;
}

List *createList(void) {
    List *h = NULL;
    char c;
    do { 
        c =(char)getchar();
        h = insertList(c, h);
    }while(c != '.');
    return h;
}

List *insertList( char val, List *t1) {
    List *t = calloc(1, sizeof( List ));
    t->val = val;
    t->next = t1;
    return t;
}

Upvotes: 1

Views: 1060

Answers (3)

arunk2
arunk2

Reputation: 2416

You are implementing insert @ begin to keep the complexity O(1).

For Doubly Linked List, you need to add another pointer 'prev' to the node and make sure the pointer to the previous node in the list. This has to be done during the insertion of node. Hence, the insert code roughly looks like below.

List *insertList( char val, List *t1) {
    List *t = calloc(1, sizeof( List ));
    t->val = val;
    t->next = t1;

    //For all nodes except the first insert, point the previous node
    if (t1 != NULL) {
       t1->prev = t;
    }
    return t;
}

I guess this should take you to next level.

Upvotes: 0

pnezis
pnezis

Reputation: 12331

The insertList should be:

List *insertList( char val, List *t1) {
  List *t = calloc(1, sizeof( List ));
  t->val = val;
  t->next = t1;
  // Set the previous pointer
  if (t1 != NULL)
     t1->prev = t;  
  return t;
}

However there is a problem with this implementation. Assume you call :

List* t1 = insertList('a', NULL)
List* t2 = insertList('b', t1)
List* t3 = insertList('c', t2)

Now you have the list

c->b->a->NULL

If you now call 

List *t4 = insertList('d', t1)

Then your "list" will be

c->b-
     \
   d->a->NULL

You see the problem here. This is not a linked list. If you just insert items at the beginning of the list your implementation is ok. In a different case you should reconsider how you insert items.

Also don't forget that you have to store the head node somewhere.

You should review the linked list Wikipedia Article and this linked lists in C/C++ tutorial

Upvotes: 0

Seth Carnegie
Seth Carnegie

Reputation: 75150

After you call insertList (inside the createList function) the forward links are set up, all you need is the backward links.

To do that, after calling insertList, you need to check if h->next is NULL, and if it's not, set h->next->prev to h. You could also do the same thing in insertList itself, by checking if t1 is NULL, and if it's not, setting t1->prev to t.

Upvotes: 0

Related Questions