Creating and Pushing Nodes in a Doubly Linked List

DLL: PUSH

Basics: Nodes are a TYPE we are defining Nodes are a complex type we are defining SO FAR: Just like int, float, double, string, etc. So they have fields: In our case: task prev next Nodes are just like the struct node you had in CIS210

Creating a new Node: When should you create a new node (on the heap)? When inserting data into your list in this case, the dll How are we inserting data? Push! So first, every time you push data, you must create a new node!!! (on the heap ) DNode *n = new DNode(t,p,h,m);

DNode *n = new DNode(t,p,h,m); First things first: every time you push data, you must create a new node!!! What this does: new: made something on the heap, returns the address of something on the heap addresses are numbers DNode *n: makes a variable n that holds an address so n hold a number the number is an address of a place on the heap If you go to the address that n holds, you will find a DNode object DNode(t,p,h,m): calls the DNode constructor If you look at the DNode constructor, it gives the DNode fields a value In our case, the node s task becomes a new Task node with t, p, h, and m and the prev and next field in the DNode are initialized to NULL

Push: BEFORE n 1) Create new Node Every time you re pushing, you re adding a new node 2) If we re doing a normal push, you d add the node to the end of the list So in this case, last s next field would be changed from NULL to 7200 n s prev would change to 5000 (the address, aka number, in last) Last now has to point to the new last node; (last has to hold the address, aka number, of n) Increase the size of the DLL (on you to do) AFTER (for a plain old push, not necessarily for our push)

Thats a typical push: Adding data to the end of a list BUT In our push, we re adding data to the end of the part of the list with a particular priority In other words, we re inserting data into a doubly linked list. How do we know where to insert? Pt 1: We look at the priority of the task field And compare it to the priority of the task field of the new node n->task->priority holds the priority of the task of the new node (in our example) Pt 2: We find where in the list nodes have the same priority as the new node s task (See next slide)

Pt 2: We must find where to insert! Where in the list nodes have the same priority as the new node s task s priority In the above example, if we are: and then a new node And the new node has a We want to insert at the end of the priority 1 nodes Think of it this way: In an emergency room, you ve got: Person A has a heart attack (priority 1) Person B has a heart attack (priority 1), Person C has a broken arm, (priority 2) and Person D has a splinter (priority 3) Person E comes in with a heart attack. You d want E to go before D and C (because a heart attack has a higher priority than a splinter or broken arm), but after A and B because they both got to the emergency room first

So were looking for the END of the nodes whose tasks have the same priority as our new node s task DNode *tmp = last; while (tmp->task->priority > n->task->priority) { // a start, but this is not complete!!!! tmp = tmp->prev; } What this does is it loops backwards from node to node Start: Tmp holds the address of the last node (5000) Then tmp gets reset to the address in the prev field of tmp (4000, and then 3000) (remember, the stuff on the right happens first, so you get the address in tmp s prev field, and then copy it over whatever is in tmp This loop stops when tmp->task->priority is no longer greater than the new node s task s priority

Now to insert the new node: tmp2 tmp 7200 7200 4000 3000 If you ve already created a new node n (Remember DNode *n = new DNode (t,p,h,m);? You ve got to do 4 things to insert the new node: 1. 2. make n s next be tmp s next (copy the address in tmp snext field to n s next field) Make tmp snext s prev point to n These two steps might be easier if you set a second temporary pointer to tmp s next Make tmp s next be n Make n s prev be tmp; 3. 4. Oh, and increase the size of the DLL!!! It has one more node now.

You must take into account: empty (there are 0 nodes in the list so far) You are pushing the very first node onto the list So both the first pointer AND the last pointer of the DLL class object should point to (aka hold the address of) the new node And, of course, the size of the list must increase

You must take into account: If tmp is NULL if tmp is NULL, it doesn t exist Things that don t exist don t have fields So if tmp is NULL, you will get an error trying to access: tmp->next tmp->prev tmp->task->priority When will tmp be NULL????

When does tmp = NULL? First Last NULL 1000 3000 NULL NULL 2000 4000 2 4000 NULL 2000 3000 5000 3 3 2 3 5000 3000 4000 2000 1000 We started by setting tmp=Last Now tmp holds 5000 (the address of the last node) Loop: while (tmp->task->priority > n->task->priority) { // you will need to modify this slightly!!! tmp = tmp->prev; } Assume n s task s priority is 1: Tmp will hold 5000, node at address 5000 s priority is 3 Tmp will hold 4000, node at address 4000 s priority is 3 Tmp will hold 3000, node at address 3000 s priority is 3 Tmp will hold 2000, node at address 2000 s priority is 2 Tmp will hold 1000, node at address 1000 s priority is 2 NOW tmp gets set to node at 1000 s prev field Gets set to NULL ASIDE: NULL does not have a prev or a next field, nor does it have a task field. BE CAREFUL of this when looping!!! So IF tmp actually becomes NULL, that means we ve looped to the beginning of the List We want to insert our new node AT THE BEGINNING of the list

So thats the update Summarizing: