doubly linked list in c
Author
i have a code segment of doubly linked list implementation:
adding a node in the middle of list
pNew -> left = pCur;
pNew -> right = pCur -> right;
pCur -> right -> left = pNew;
pCur -> right = pNew;
what is the purpose of the last line of abive code???
Doesn`t it make this list a circular one, while it should be doubly linked list.
Without that pCur->right would refer to the next node after pNew, and coming from the left you wouldn't know pNew is there.
Lets draw it out:
Looks correct to me! Did you follow it?
Start: (left pointers come out near the top of a node and right pointers come out near the bottom) +------+ | | | pNew | | | +------++------+ +------+| | ---------------> | || pCur | | X || | <--------------- | |+------+ +------+pNew -> left = pCur; +------+ +------- | | | | pNew | | | | | +------+ V+------+ +------+| | ---------------> | || pCur | | X || | <--------------- | |+------+ +------+pNew -> right = pCur -> right; +------+ +------- | | | | pNew | | | | --------+ | +------+ | V V+------+ +------+| | ---------------> | || pCur | | X || | <--------------- | |+------+ +------+pCur -> right -> left = pNew;//pCur->right points to the node I've marked as X,//so the above is the same as X->left = pNew +------+ +------- | | | | pNew | | | | --------+ | +------+ | V V ^+------+ | +------+| | --------+------> | || pCur | | | X || | +------- | |+------+ +------+pCur -> right = pNew; +------+ +------- | | | | pNew | | | | --------+ | +------+ | V V ^ ^+------+ | | +------+| | ------+ | | || pCur | | | X || | +------ | |+------+ +------+Looks correct to me! Did you follow it?
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
