OSU CSE 2421
Think about the problem in a different way
J.E.Jones
OSU CSE 2421
The previous linked list insert code thinks in terms of nodes: ◦ “Put this new node between these two nodes”
That gives us a previous and a traverse pointer
That gives us special cases
◦ Empty list
◦ Insert at the front of the list
◦ Insert at the end of the list (maybe)
The code is long but straightforward if you keep track of what case you are in
J. E. Jones
OSU CSE 2421
Let us think in terms of pointers to nodes instead of nodes
The head pointer is no longer a special case, it has the same type as a next pointer
To do the insert, exactly one existing pointer in the list needs to change because something needs to point to the new node
That one existing pointer holds the value that the new node’s next pointer needs
J. E. Jones
OSU CSE 2421
Insert boils down to:
◦ Find the pointer that needs to change
◦ Give that value to the new node’s next pointer
◦ Set the pointer that needs to change to point to the new node
There are no special cases at all
The code is short (4 lines)
The code is dense
The code is harder to understand, write, debug, and maintain The code optimizes very well
The code is “elegant”
J. E. Jones
OSU CSE 2421
We exploit the fact that we can take the address of a pointer ◦ This gives us a pointer to a pointer
◦ Doing so demands careful attention to type:
Node
Pointer to node
Pointer to pointer to node
◦ Doing so demands careful dereferencing (see above)
We exploit pass by value to give us a perfectly initialized local variable
◦ A pointer that points to the head pointer is no different than a pointer that points to a next pointer
We exploit short-circuit evaluation to protect dereferencing
J. E. Jones
OSU CSE 2421
Node { struct Data dval; Node *next;} ; Node *head = NULL, *newnode = NULL;
/* assume we allocate the new node and populate the ** data values in that node. Now we insert it:
*/
Note same data type!
insert( &head, newnode);
/* C is pass by value, so we must pass the address ** of the head pointer since we intend to change it */
J. E. Jones
OSU CSE 2421
You may not use the following code in your Lab 4 submission.
J. E. Jones
OSU CSE 2421
Node{ struct Data dval; Node *next;} ;
insert(Node**p2p2change, Node *newnode) {
#ifdef DEBUG
#endif
#ifdef DEBUG
#endif
#ifdef DEBUG
#endif }
J. E. Jones
printf(“inserting %d (lives at 0x%x)\n”, newnode->dval.key, newnode );
/* skip nodes with bigger key than key to insert */
while( *p2p2change != NULL && (**p2p2change).dval.key > newnode->dval.key) {
printf(“Going past %d\n”, (**p2p2change).dval.key);
p2p2change = &((**p2p2change).next); }
/* do the insert: */
/* make new node next point to what the changing pointer currently points to */ newnode->next = *p2p2change;
/* make the pointer to change point to the new node */
*p2p2change = newnode;
printf(“Setting change to 0x%x, next to 0x%x\n”, *p2p2change, newnode->next);
OSU CSE 2421
Node{ struct Data dval; Node *next;} ;
insert(Node**p2p2change, Node *newnode) {
#ifdef DEBUG
#endif
#ifdef DEBUG
#endif
#ifdef DEBUG
#endif }
J. E. Jones
printf(“inserting %d (lives at 0x%x)\n”, newnode->dval.key, newnode );
/* skip nodes with bigger key than key to insert */
while( *p2p2change != NULL && (**p2p2change).dval.key > newnode->dval.key) {
printf(“Going past %d\n”, (**p2p2change).dval.key);
p2p2change = &((**p2p2change).next); }
/* do the insert: */
/* make new node next point to what the changing pointer currently points to */ newnode->next = *p2p2change;
/* make the pointer to change point to the new node */
*p2p2change = newnode;
printf(“Setting change to 0x%x, next to 0x%x\n”, *p2p2change, newnode->next);
OSU CSE 2421
while( *p2p2change != NULL
We have a pointer to a pointer, so we dereference one time to get a pointer to a node
If the pointer we are pointing at is NULL,
1. there is either nothing in the list (head is NULL) or
2. we hit the end of the list (some next pointer is NULL)
In either case we stop here, and this pointer will point to the new node and the new node next will get set to NULL and our new node is at the end of the list.
J. E. Jones
OSU CSE 2421
p2p2change NULL
while( *p2p2change != NULL
• Ifthepointerwearelookingatis NULL, we have found the right spot for insert
• Thispartofthewhileloopistrue when:
• Wereachedtheendofalistwith many nodes, or
• Thelistisempty
J. E. Jones
OSU CSE 2421
Node{ struct Data dval; Node *next;} ;
insert(Node**p2p2change, Node *newnode) {
#ifdef DEBUG
#endif
/* skip nodes with bigger key than key to insert */
#ifdef DEBUG
#endif
printf(“Going past %d\n”, (**p2p2change).dval.key);
#ifdef DEBUG
#endif }
printf(“Setting change to 0x%x, next to 0x%x\n”, *p2p2change, newnode->next);
printf(“inserting %d (lives at 0x%x)\n”, newnode->dval.key, newnode );
while( *p2p2change != NULL && (**p2p2change).dval.key > newnode->dval.key) {
p2p2change = &((**p2p2change).next); }
/* do the insert: */
/* make new node next point to what the changing pointer currently points to */ newnode->next = *p2p2change;
/* make the pointer to change point to the new node */
*p2p2change = newnode;
J. E. Jones
OSU CSE 2421
&& (**p2p2change).dval.key > newnode->dval.key
Short circuit evaluation prevents this expression from being evaluated if the pointer(address) p2p2change points to is NULL (see previous slides)
Since it is not NULL, we can dereference the pointer to a pointer 2 times to get to a node.
We can thus compare the data value (key) of the node pointed at by the pointer, p2p2change, points to with the data value (key) in the new node.
If the new data value is larger, the condition fails, stopping us at the right spot in the list (list is ordered biggest first (i.e. descending order))
J. E. Jones
OSU CSE 2421
Node{ struct Data dval; Node *next;} ;
insert(Node**p2p2change, Node *newnode) {
#ifdef DEBUG
#endif
/* skip nodes with bigger key than key to insert */
#ifdef DEBUG
#endif
printf(“Going past %d\n”, (**p2p2change).dval.key);
#ifdef DEBUG
#endif }
printf(“Setting changed to 0x%x, next to 0x%x\n”, *p2p2change, newnode->next);
printf(“inserting %d (lives at 0x%x)\n”, newnode->dval.key, newnode );
while( *p2p2change != NULL && (**p2p2change).dval.key > newnode->dval.key) {
}
p2p2change = &((**p2p2change).next);
/* do the insert: */
/* make new node next point to what the changing pointer currently points to */ newnode->next = *p2p2change;
/* make the pointer to change point to the new node */
*p2p2change = newnode;
J. E. Jones
OSU CSE 2421
p2p2change = &((**p2p2change).next);
We know that we can double dereference p2p2change (see previous slide). That takes us to a node (innermost parentheses)
We can get to the next pointer of that node with .next
◦ There are alternative ways to code this
◦ The syntax here emphasizes type
◦ There are many ways to code this that look right, compile, and fail
We don’t want the value of the next pointer since we aren’t dealing in nodes. We want the address of the next pointer which we get with the outer &
J. E. Jones
OSU CSE 2421
p2p2change &B
• p2p2change= &((**p2p2change).next);
B &C
C &D
D NULL
• Movep2p2changetopointtothe next pointer of the node pointed to by the pointer we are looking at
• Note:p2p2changedoesnotpoint at the node, it points at the next pointer in the node
J. E. Jones
OSU CSE 2421
p2p2change &B
• p2p2change= &((**p2p2change).next);
B &C
C &D
D NULL
• Movep2p2changetopointtothe next pointer of the node pointed to by the pointer we are looking at
• Note:p2p2changedoesnotpoint at the node, it points at the next pointer in the node
J. E. Jones
OSU CSE 2421
Node{ struct Data dval; Node *next;} ;
insert(Node**p2p2change, Node *newnode) {
#ifdef DEBUG
#endif
/* skip nodes with bigger key than key to insert */
#ifdef DEBUG
#endif
printf(“Going past %d\n”, (**p2p2change).dval.key);
#ifdef DEBUG
#endif }
printf(“Setting changed to 0x%x, next to 0x%x\n”, *p2p2change, newnode->next);
printf(“inserting %d (lives at 0x%x)\n”, newnode->dval.key, newnode );
while( *p2p2change != NULL && (**p2p2change).dval.key > newnode->dval.key) {
p2p2change = &((**p2p2change).next); }
/* do the insert: */
/* make new node next point to what the changing pointer currently points to */ newnode->next = *p2p2change;
/* make the pointer to change point to the new node */
*p2p2change = newnode;
J. E. Jones
OSU CSE 2421
newnode->next = *p2p2change; *p2p2change = newnode;
Whatever value the pointer we have a pointer to has, we want the new node’s next pointer to also point there.
◦ It could be NULL
◦ It could point to a node with a smaller data value
We need to do the actual insert by changing the pointer that needs to change ◦ We dereference once to get to that pointer
◦ We set it to point to the new node
J. E. Jones
OSU CSE 2421
p2p2change
• First set newnode->next to point where the pointer we are looking at points
&C B NULL
• newnode->next = *p2p2change;
newnode
C &D
D NULL
• Then change the pointer we are looking at so that it points to the new node
• *p2p2change = newnode;
J. E. Jones
OSU CSE 2421
p2p2change
B &C newnode
• *p2p2change = newnode;
&C
• newnode->next = *p2p2change;
C &D
D NULL
• First set newnode->next to point where the pointer we are looking at points
• Then change the pointer we are looking at so that it points to the new node
J. E. Jones
OSU CSE 2421
p2p2change
• First set newnode->next to point where the pointer we are looking at points
B &C newnode
• *p2p2change = newnode;
&B
• newnode->next = *p2p2change;
C &D
D NULL
• Then change the pointer we are looking at so that it points to the new node
J. E. Jones
OSU CSE 2421
If you understand pointers to pointers and all the other C language details, it’s hard to beat a 4-line linked list insert routine
If you don’t understand any single bit of the code, it becomes incomprehensible and thus worthless
Industry code out there comes in 3 flavors
◦ Too simple and thus long and tedious
◦ Just right
◦ Too clever and impossible to touch without wholesale replacement
J. E. Jones
OSU CSE 2421
The same analysis works for delete:
Somewhere in the list we might have pointers that will need to change because they point to nodes that need to be deleted
Those pointers need to be set to point wherever the node being deleted pointed to
We probably need to deal with the node itself before we burn all the pointers, we have that point to it
J. E. Jones
OSU CSE 2421
The code is 1 while loop – stop on NULL pointer
There is 1 if statement inside the while loop – do we delete this node?
There are no special cases
A single local variable is helpful so that we still have a pointer to any node we want to delete after we remove that node from the list. This way we can properly dispose of the node.
See diagrams to follow
J. E. Jones
OSU CSE 2421
p2p2change NULL
• If the pointer we are looking at is NULL, we are done
holder
J. E. Jones
OSU CSE 2421
&B
• It could be the head pointer, or it could be the next pointer of a previous node
B &C
C &D
D NULL
• Movep2p2changetopointtothe next pointer of the node pointed to by the pointer we are looking at
holder
• Thepointerwearelookingatholds the address of B
• SincenodeBstays,thepointerwe are looking at won’t change
J. E. Jones
OSU CSE 2421
&B
• It could be the head pointer, or it could be the next pointer of a previous node
B &C
C &D
D NULL
• Movep2p2changetopointtothe next pointer of the node pointed to by the pointer we are looking at
holder
• Thepointerwearelookingatholds the address of B
• SincenodeBstays,thepointerwe are looking at won’t change
J. E. Jones
OSU CSE 2421
&B
B &C
C &D
D NULL
holder
• First set the holder to point to the node so we can properly dispose of it
J. E. Jones
OSU CSE 2421
&B
B &C
C &D
D NULL
Holder
• First set the holder to point to the node so we can properly dispose of it
J. E. Jones
OSU CSE 2421
&C
• Do not change p2p2change – it is possible that node C will be deleted on the next iteration of the loop. If that is the case, we are right now looking at a pointer that will need to change.
B &C
C &D
D NULL
holder
• First set the holder to point to the node so we can properly dispose of it
• Then change the pointer we are looking at so that it points to the next node
J. E. Jones
OSU CSE 2421
The code for this delete is left for the student
J. E. Jones