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

Question

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;
}

forgive me if I am wrong but this seems like a homework problem, if so it should be tagged accordingly — slayton
– slayton, Commented Nov 18, 2011 at 19:09

Seth Carnegie · Accepted Answer · 2011-11-18 18:50:09Z

0

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.

edited Nov 18, 2011 at 18:50

answered Nov 18, 2011 at 18:45

Seth Carnegie

75.3k22 gold badges185 silver badges252 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

pnezis · Accepted Answer · 2011-11-18 19:08:04Z

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

arunk2 · Accepted Answer · 2017-04-22 11:19:43Z

0

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.

answered Apr 22, 2017 at 11:19

arunk2

2,4563 gold badges25 silver badges35 bronze badges

Collectives™ on Stack Overflow

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

3 Answers 3

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related