[SOLVED] CS Java OSU CSE 2421

OSU CSE 2421
Required Reading: Pointers On C, Chapter 12, Sections 12.1 through 12.2.2
J.E.Jones

OSU CSE 2421
Previously, we saw how to declare a struct with a pointer to a struct of the same type. This kind of struct variable can be used as a node in a linked list. The node typically has two members:
One member, called data, is a C struct which is used to store data of interest. The other member, called next, is a pointer to a struct Node. For example:
struct Data {
char first_name[15]; char last_name[15]; int idNumber;
Note that within typedef creation for Node, we must use struct Node * because the typedef is not yet complete.
};
typedef struct Node{
struct Data student;
struct Node *next; }Node;
The linked list will be constructed by creating a number of these nodes dynamically, one at a time, and linking them to each other with the next pointer.
J. E. Jones

OSU CSE 2421
The structure of a linked list is more complicated than an array, and more work is required to construct and maintain a linked list.
Nonetheless, depending on the application, linked structures often have advantages.
Some say Linear linked structures (linked lists) are not so commonly used in real applications (I disagree), but they are simpler to construct and manipulate than binary (search) trees, so we will only work with a linear, singly-linked list here.
Binary search trees have significant advantages compared with (sorted) arrays in many cases, such as faster insertion and deletion times, but comparable search performance.
J. E. Jones

OSU CSE 2421
Using the nodes that we have introduced before, what else do we need to construct a linked list?
Only one thing: Node * list_head, to point to the first node in the list: Node *list_head = NULL; /*Set list head pointer to NULL initially
to show list is empty */
We only want the Node * rather than a whole Node here to keep space efficiently.
NOTE: This is different from Java where you just use an empty node
To construct the list, we will make the list_head pointer point to the first node, the next member of the first node point to the second node, . . . . the next member of the n 1st node point to the nth (last) node, and the next member of the nth (last) node point to no node (make it a NULL pointer).
Making the next member of the last node point to NULL will allow us to detect where the end of the list is (and avoid segmentation faults!). This is analogous to ending a character string with a NULL character.
J. E. Jones

OSU CSE 2421
Before we look at the details of insertion into the list, we need to consider the list_head pointer more carefully.
Various functions will have to know the address in the list_head pointer in order to do things with the list (insert nodes, delete nodes, process data in the nodes, print data in the nodes, etc.).
If we make the list_head pointer a file scope (global) variable, we do not have to pass it as a parameter to these functions.
This, however, is currently an unacceptable way to write software and should only be done in very limited cases (this is not one of them)! Debugging and maintenance are MUCH more difficult with global variables.
You are not allowed to use file scope variables in software you write for this course.
Therefore, in general, the functions in your linked list program will have to be passed the list_head pointer, which is declared in main, as a parameter, if they need to access data in the list or modify the list in any way.
The challenge for each of you is to determine whether the list_head pointer should be passed by value or by reference to each function that requires it.
J. E. Jones

OSU CSE 2421
We need to think about whether the function may need to modify (change) the list_head pointer or if it only needs to read it.
If it needs to potentially modify it, we cannot pass the head pointer by value. Why?
Which functions might need to modify the head pointer? Keep this question in mind as we look at the following slides.
J. E. Jones

OSU CSE 2421
/* Here are the necessary declarations for a Node of the type declared above, and for a head pointer */
struct Data {
char first_name[15];
char last_name[15]; int id_number;
int first_semester; struct grades *list;
These can be put in a .h file
};
typedef struct Node {
struct Data student;
struct Node *next; }Node;
scanf(%s, (newNodePtr->student.first_name)); /*Initialize list_head to NULL since list is empty at first. */
Node *list_head = NULL;
This must be a block scope variable
Note: no structures of type Node have yet been declared or dynamically allocated, only space for a head pointer has been allocated.
J. E. Jones

OSU CSE 2421
/*With the declarations above, to create a new Node, we can use the following */
Node *newNodePtr;
newNodePtr = (Node *)malloc (sizeof (Node)); if (newNodePtr == NULL) {
} else {
}
. . . . /*The storage was NOT allocated, so print an error message and exit */
. . . . /* The storage was allocated, and we can use the Node */
. /*Callafunctiontogetthedataforthenodeandstoreitinthenode*/
getDataForNode(newNodePtr); /* why can we just pass the Node address?
why we dont need to pass &newNodePtr ? */
/* then we can put this new Node into the linked list */
insertNode(&list_head, newNodePtr);
Note: When we read the data from input which is to be stored in the node, we can read it directly into the node (how?), rather than storing it in another variable, and then assigning that variable to the node.
J. E. Jones

OSU CSE 2421
White space can be an issue, since scanf() can read both numeric data (ints and floats) and non-numeric data (strings).
Keep in mind that scanf() ignores leading white space characters (space, tab, etc.) for numeric data, but not for non-numeric data in the way we will read it (we will be reading strings which have white space characters).
Therefore, if you are reading numeric data, you do not have to be concerned about consuming preceding newlines, because scanf() will take care of it for you (it consumes any whitespace characters before the 1st digit).
Where might you find a preceding newline ?????
If you are reading non-numeric data, however, you will have to consume any preceding newlines, because scanf() will not consume them.
Youve seen this in each lab so far, but I wanted to remind you again
J. E. Jones

OSU CSE 2421
Typically, we want a list in some sorted order so you must identify what value your linked list node contains that you want to use as your sort key
Once you have determined your sort key, you must decide how to represent your key so that your sort order is quick to calculate
How would you create a sort key for month/day/year when multiple years are involved?
For example, years 1950 through (potentially) 2099. Thoughts?
J. E. Jones

OSU CSE 2421
Would this work??? union date_key {
} }dateKey;
int key; /* a 4-byte key */ struct{
char day; char month; short year;
/* 1-31 */ /* 1-12 */ /*1950-2099 */
J. E. Jones

OSU CSE 2421
union date_key {
int key;
/* a 4-byte key*/
}dateKey;
8-bits
8-bits
16-bits
1-31
1-12
1950-2099
0001 0101 (21)
0000 1000 (8)
1100 1100 0000 0111 (1996)
struct{
char day; char month; short year; }
/* 1-31, these values fit in 8 bits */ /* 1-12, these values fit in 8 bits */ /* 1950-2099, these values fit in 16 bits */
-2w-1 through 2w-1-1 says these values fit
dateKey.key=0x07CC0815 = 130,811,925
note this only works in Little Endian, so not portable
J. E. Jones

OSU CSE 2421
What about just int dateKey; ??? Can we still put in separate fields???
16-bits
8-bits
8-bits
1950-2099
1-12
1-31
0000 0111 1100 1100 (1996)
0000 1000 (8)
0001 0101 (21)
This is the way it would look if we were just reading the value from left to right.
J. E. Jones

OSU CSE 2421
int dateKey;
int day, month, year;
scanf(%d/%d/%d, &month, &day, &year);
Input: 8/21/1996 dateKey=year;
0000 0000 0000 0111 0000 0000 0000 0111
0000 0000 0000 0111 1100 1100 1100 1100 0000 0000 0000 0000 0000 0000 0000 1000 0000 0000 1100 1100 0000 1000 0000 0000
dateKey <<=16;month <<=8;dateKey |=month;dateKey |=day;0000 01111100 1100 0000 1000 0001 0101dateKey=0x07CC0815 = 130,811,925 note this works in Big or Little Endian1100 1100 0000 1000 0001 0101 (1996) (8) (21)0000 0111J. E. Jones OSU CSE 2421int dateKey;int day, month, year;year = dateKey;year = (unsigned)year >>16;
0000 0111 1100 1100 0000 1000 0001 0101 0000 0000 0000 0000 0000 0111 1100 1100
month = dateKey;
0000 0111 1100 1100 0000 1000 0001 0101 0000 0000 0000 0000 0000 1000 0000 0000 0000 0000 0000 0000 0000 0000 0000 1000
month &=0x0000ff00;
month = (unsigned)month>>8;
day= dateKey;
day &=0x000000ff;
0000 0111 1100 1100 0000 1000 0001 0101 0000 0000 0000 0000 0000 0000 0001 0101
Why do we have to cast year and month to unsigned??
J. E. Jones

OSU CSE 2421
If we want to insert a node into the list, what do we need to do?
We will assume that the nodes in the list will be ordered in ascending order based on some member in the data member of the node (assume its an integer).
First, we have to create the new node (as shown above), and initialize the members of the data member of the Node
Then, we have to call the insert function, and pass it the current list (how?), and the new node (how?).
In the insert function, declare a pointer to traverse (go through) the list: Node *traversePtr;
Set the traversePtr to point to the same address the list_head pointer points to, so that you start looking at the beginning of the list.
How might we do these things??
J. E. Jones

OSU CSE 2421
If we want to insert a node into the list, what do we need to do?
We will assume that the nodes in the list will be ordered in ascending order based on some member in the data member of the node (assume its an integer).
First, we have to create the new node (as shown above), and initialize the members of the data member of the Node
Then, we have to call the insert function, and pass it the current list (how?), and the new node (how?). insert(&list_head, newNodePtr);
Prototype for insert function would be
insert(Node **list_head_ptr, Node *newNodePtr);
In the insert function, declare a pointer to traverse (go through) the list: Node *traversePtr;
Set the traversePtr to point to the same address the list_head pointer points to, so that you start looking at the beginning of the list.
traversePtr = *list_head_ptr;
J. E. Jones

OSU CSE 2421
When we traverse the list to determine where to insert, there are three possible cases or situations:
1) The list is empty (list_head is a NULL pointer).
To insert, make list_head point to the inserted node. That is,
list_head = address of node we wish to insert.
*list_head_ptr = newNodePtr;
Make the next pointer of the inserted node point to NULL (it may have been initialized to NULL during data entry, but if not, this needs to be done here).
newNodePtr->next = NULL;
J. E. Jones

OSU CSE 2421
list_head_ptr Node *list_head NULL
newNodePtr
NULL
next
J. E. Jones

OSU CSE 2421
*list_head_ptr = newNodePtr; list_head_ptr list_head
newNodePtr
NULL
next
J. E. Jones

OSU CSE 2421
2) The list already has one or more nodes, and the new node needs to be inserted as the first node in the list.
How?
IN THIS ORDER
A. The current address in list_head must be copied to the *next member in the newNodePtr structure
newNodePtr->next = *list_head_ptr;
B. The value of list_head must be changed to the address of newNodePtr.
*list_head_ptr = newNodePtr;
J. E. Jones

OSU CSE 2421
newNodePtr->next = *list_head_ptr; list_head_ptr list_head
newNodePtr
next
next
Prior to executing the instruction above, this is what we have
NULL
J. E. Jones

OSU CSE 2421
newNodePtr->next = *list_head_ptr; list_head_ptr list_head
newNodePtr
next
next
At this point, both list_head and newNodePtr->next point to the same place
NULL
J. E. Jones

OSU CSE 2421
*list_head_ptr = newNodePtr;
list_head_ptr list_head
newNodePtr
next
Now list_head points to newNodePtr; and newNodePtr->next points to all following Nodes
next
NULL
J. E. Jones

OSU CSE 2421
3. Non-exception case. i.e. The new Node belongs somewhere between two existing Nodes.
we traverse the list to search for where to insert the node. To do so, we must maintain a pointer to the node before the node where we are
(see below):
Node *priorNode;
use the traversePtr previously declared to point to the Node we are
currently looking at
So, traverse the list, node by node, to find out the correct place to insert the node based on our sort key;
advance traversePtr and priorNode through the list.
When traversing, we need to check that the traverse pointer is not NULL before trying to access members of the node to which it points. If it is NULL, we have reached the end of the list, and should insert the new node there (as described below).
When the correct place is found, change these pointers (in this order!): a. The next pointer of the node to be inserted:
newNodePtr->next = traversePtr;
b. The next pointer of the node after which the new node is being inserted (this is priorNode->next): priorNode->next = newNodePtr;
J. E. Jones

OSU CSE 2421
priorNode
traversePtr
next
next
newNodePtr
next
J. E. Jones

OSU CSE 2421
newNodePtr->next = traversePtr;
priorNode
traversePtr
next
next
newNodePtr
At this point both priorNode and newNodePtr point to traversePtr
next
J. E. Jones

OSU CSE 2421
priorNode->next = newNodePtr;
priorNode
traversePtr
next
next
newNodePtr
At this point newNodePtr is inserted in the linked list
next
J. E. Jones

OSU CSE 2421
If we want to delete a node from the list, what do we need to do?
Declare a pointer to traverse the list: Node *traversePtr;
Set the traversePtr to point to the same address the list_head pointer points to.
traversePtr = *list_head_ptr;
J. E. Jones

OSU CSE 2421
When we traverse the list to find the node to be deleted, there are 3 possible situations:
1. The list is empty: ERROR There are no nodes, so there is nothing to be deleted! Print an error message informing the user that they have tried to delete a non-existent node.
J. E. Jones

OSU CSE 2421
2. Node to delete is at the front of the linked list
Check to see if the node to be deleted is the first node. If so, in order to
delete it, do these things, in this order:
Make the list_head pointer point to the same thing as traversePtr->next, then free(traversePtr);
traversePtr = *list_head_ptr;
*list_head_ptr = traversePtr->next;
*list_head_ptr = (*list_head_ptr)->next; free(traversePtr);
J. E. Jones

OSU CSE 2421
list_head_ptr Node *list_head
traversePtr
next
next
J. E. Jones

OSU CSE 2421
*list_head_ptr = traversePtr->next;
list_head_ptr list_head
traversePtr
next next
J. E. Jones

OSU CSE 2421
free(traversePtr);
list_head_ptr list_head
next
J. E. Jones

OSU CSE 2421
3. Non-exception case. i.e. The Node to delete is somewhere between two existing Nodes or at the end. Both cases can be handled this way.
traverse the list to search for the node to be deleted, we must maintain a pointer to the node before the node where we are:
struct Node *priorNode;
advance traversePtr and priorNode to go through the list.
When traversing, we need to check that the traverse pointer is not NULL before trying to access members of the node to which it points.
If it is NULL, the node is not in the list. Print an error message to the user.
If the node is found, do these actions in this order:
a. Change the next pointer of prior node (the node before the node
which is being deleted): priorNode->next = traversePtr->next;
b. Call free() with the pointer to the node being deleted (what pointer is this?).
J. E. Jones

OSU CSE 2421
priorNode
traversePtr->next
next
next
traversePtr
Node to delete next
J. E. Jones

OSU CSE 2421
priorNode->next = traversePtr->next;
priorNode traversePtr->next
next next
traversePtr
Node to delete next
At this point, both priorNode->next and traversePtr->next point to the same thing, but were getting ready to free traversePtr.
J. E. Jones

OSU CSE 2421
Free(traversePtr);
priorNode traversePtr->next
next next
J. E. Jones

OSU CSE 2421
Besides insertion and deletion, there are some other kinds of operations we can identify on linked lists:
List traversal for some purpose:
Find an element in the list and print out the related data. Print all the items in the list.
Do computations on the data in the list, such as totaling all the items, counting the number of items in the list, computing averages, finding minimum and maximum values, etc.
In general, traversing the list for these purposes is less complicated than it is for insertion and deletion, because we do not have to keep track of the prior node; we can declare a traversePtr and make it point to the beginning of the list and then go through the entire list.
Do you think you would need to pass the list_head by reference or by value to these type functions?
We do, however, must still ensure that we do not try to access nodes beyond the end of the list (you should now be able to figure out how to do this)!
J. E. Jones

OSU CSE 2421
Before your program terminates, you should call free() to return the space for all the nodes, which were allocated as the program was running.
Best practice is to m/calloc() a node just as you need the space and call free() for each node as soon as there is no longer a need for it. Think of pulling a paper cup from the stack, using it, then throwing it away when done.
Ive had students put together a neat little recursive function to free Nodes from a linked list prior to their program ending, but there is a much simpler, less resource costly way to do it by just traversing down the linked list freeing Nodes as you go.
J. E. Jones