CIS3355:
Business Data Structures
Fall, 2008
|
|
|
What is a linked list by definition according to programming? A data structure in which each element contains a pointer to the next element, thus forming a linear list. Basically link lists allow us to command and exhibit the contents of information without having to physically sort the list. This procedure would consume a large amount of time especially if it was a large database. This can be a huge advantage especially when the contents of information in record form may be viewed in various orders.
What is a linked list? A linked list is a chain of structures or records called nodes. Each node has at least two members, one of which points to the next item or node in the list! These are defined as Single Linked Lists because they only point to the next item, and not the previous. Those that do point to both are called Doubly Linked Lists or Circular Linked Lists. In a linked list, each item is allocated space as it is added to the list. A link is kept with each item to the next item in the list. 'Each node has two elements. 1. the item being stored in the list and 2. a pointer to the next item in the list. The last node in the list contains a NULL pointer to indicate that it is the end or tail of the list. As items are added to a list, memory for a node is dynamically allocated. Thus the number of items that may be added to a list is limited only by the amount of memory available. The variable which represents the list is simply a pointer to the node at the head of the list. The simplest strategy for adding an item to a list is to: a) allocate space for a new code. b) copy the item into it c) make the new node's nest pointer point to the current head of the list and d) make the head of the list point to the newly allocated node. This strategy is fast and efficient, but each item is added to the head of the list. Singly Linked List Advantages Allow for display in order w/o sorting, can order on any field, Easy to establish and maintain, Need not search until list end if an Element is not on the list. Doubly Linked List Advantages In addition to the above, can search & display from either end. On the Contrary, there is a great difference between Double
Linked lists and Circular Linked lists and don't forget Singly
Notice that we define a default constructor for our structure
that sets Next equal to NULL. This is because we need to know when we have
reached the end of our linked list. Each Next item that is NOT equal to
NULL means that it is pointing to another allocated instance. If it does
equal NULL, then we have reached the end of our list.
We can actually add nodes in two possible places, the
beginning or the end, although the standard seems to be th What does the code show? The code below shows some key routines to implement a doubly linked list. The NODE structure represents each node in the list. It includes an integer for storing information and a pointer to the next and previous nodes in the list. Obviously, you can modify the NODE structure to store other types of data and this code is ideally suited for conversion to a template that can be compiled to work with any other type of data. In addition, all the list-related routines are ideally suited to be implemented as a class. I kept the code as straight C here just to keep things as simple as possible and to fit the code into the space I had available. Perhaps you can modify it to meet your own needs. #include
struct NODE {
NODE *pNext;
NODE *pPrev;
int nData;
};
NODE *pHead, *pTail;
// Appends a node to the end of the list
void AppendNode(NODE *pNode)
{
if (pHead == NULL) {
pHead = pNode;
pNode->pPrev = NULL;
}
else {
pTail->pNext = pNode;
pNode->pPrev = pTail;
}
pTail = pNode;
pNode->pNext = NULL;
}
// Inserts a node into the list after pAfter
void InsertNode(NODE *pNode, NODE *pAfter)
{
pNode->pNext = pAfter->pNext;
pNode->pPrev = pAfter;
if (pAfter->pNext != NULL)
pAfter->pNext->pPrev = pNode;
else
pTail = pNode;
pAfter->pNext = pNode;
}
// Removes the specified node from the list
void RemoveNode(NODE *pNode)
{
if (pNode->pPrev == NULL)
pHead = pNode->pNext;
else
pNode->pPrev->pNext = pNode->pNext;
if (pNode->pNext == NULL)
pTail = pNode->pPrev;
else
pNode->pNext->pPrev = pNode->pPrev;
}
// Deletes the entire list
void DeleteAllNodes()
{
while (pHead != NULL)
RemoveNode(pHead);
}
void main()
{
NODE *pNode;
// Add items to linked list
for (int i = 0; i < 100; i++) {
pNode = new NODE;
pNode->nData = i;
AppendNode(pNode);
}
// Now display each item in list
for (pNode = pHead; pNode != NULL; pNode = pNode->pNext) {
printf("%d\n", pNode->nData);
}
//
DeleteAllNodes();
}
LINKED LISTS -------- -------- | data | --->| data | |--------| | |--------| | pointer|---- | pointer| ---> NULL -------- -------- A structure which contains a data element and a pointer to the next node is created by, struct list {
int value; struct list *next; }; This defines a new data structure called list (actually the definition of a node), which contains two members. The first is an integer called value. The second is called next, which is a pointer to another list structure (or node). Suppose that we declare two structures to be of the same type as list, eg, struct list n1, n2; The next pointer of structure n1 may be set to point to the n2 structure by /* assign address of first element in n2 to the pointer next of the n1 structure */ n1.next = &n2; which creates a link between the two structures. /* LLIST.C Program to illustrate linked lists */ #include <stdio.h> struct list {
int value; struct list *next; }; main() {
struct list n1, n2, n3; int i; n1.value = 100; n2.value = 200; n3.value = 300; n1.next = &n2; n2.next = &n3; i = n1.next->value; printf("%d\n", n2.next->value);
} Not only this, but consider the following n1.next = n2.next /* deletes n2 */ n2_3.next = n2.next; /* adds struct n2_3 */ n2.next = &n2_3; In using linked list structures, it is common to assign the value of 0 to the last pointer in the list, to indicate that there are no more nodes in the list, eg, n3.next = 0; /* Program to illustrate traversing a list */ #include <stdio.h> struct list {
int value; struct list *next; }; main() {
struct list n1, n2, n3, n4; struct list *list_pointer = &n1; n1.value = 100; n1.next = &n2; n2.value = 200; n2.next = &n3; n3.value = 300; n3.next = &n4; n4.value = 400; n4.next = 0; while( list_pointer != 0 ) {
printf("%d\n", list_pointer->value);
list_pointer = list_pointer->next; } } This program uses a pointer called list_pointer to cycle through the linked list. 1. Define a structure called node, which contains an integer element called data, and a pointer to a structure of type node called next_node. struct node {
int data; struct node *next_node; }; 2. Declare three structures called node1, node2, node3, of type node. struct node node1, node3, node3; 3. Write C statements which will link the three nodes together, with node1 at the head of the list, node2 second, and node3 at the tail of the list. Assign the value NULL to node3.next to signify the end of the list. node1.next_node = &node2; node2.next_node = &node3; node3.next_node = (struct node *) NULL; 4. Using a pointer list, of type node, which has been initialised to the address of node1, write C statements which will cycle through the list and print out the value of each nodes data field. while( list != NULL ) {
printf("%d\n", list->data );
list = list->next_node; } 5. Assuming that pointer list points to node2, what does the following statement do? list->next_node = (struct node *) NULL; The statement writes a NULL into the next_node pointer, making node2 the end of the list, thereby erasing node3 from the list. 6. Assuming the state of the list is that as in 3., write C statements which will insert a new node node1a between node1 and node2, using the pointer list (which is currently pointing to node1). Assume that a pointer new_node points to node node1a. new_node.next_node = list.next_node; list.next_node = new_node; 7. Write a function called delete_node, which accepts a pointer to a list, and a pointer to the node to be deleted from the list, eg void delete_node( struct node *head, struct node *delnode ); void delete_node( struct node *head, struct node *delnode ) {
struct node *list; list = head; while( list->next != delnode ) {
list = list->next; list->next = delnode->next; } 8. Write a function called insert_node, which accepts a pointer to a list, a pointer to a new node to be inserted, and a pointer to the node after which the insertion takes place, eg void insert_node( struct node *head, struct node *newnode, struct node *prevnode ); void insert_node( struct node *head, struct node *newnode, struct node *prevnode ) {
struct node *list; list = head; while( list != prevnode ) list = list->next; newnode->next = list->next; list->next = newnode; }
Given the record structure and that &student[2] is 7828:
Each record requires: 11 + 28 + 30 + 2 + 2 + 4 + 4 + 4 + 4 = 89 bytes of storage. The base address of the array would be: 7828 – 2 * 89 = 7828 – 178 = 7650
The linked list would thus appear as:
And the contents of the variables first and last are:
Therefore: Yields: a. printf(“%lu\n”,first); 7917 b. printf(“%lu\n”,last); 7828 c. printf(“%s\n”, first->address); 20 Wall St. d. printf(“%lu\n”,&student[1].balance); 7739 + 11 + 28 + 30 + 2 + 2 + 4 = 7816 e. printf(“%f5.2\n”,student[3].next->balance); 8006 -> 0.00 (Carnegie’s Balance) f. printf(“%lu\n”, ++first); Prefix notation: 7917 + 89 = 8006 g. printf(“%d\n”,last->previous->age); 7828 -> 7650 -> 38 (Gate’s age)
References: http://www.inversereality.org/tutorials/c++/linkedlists.html http://http://ciips.ee.uwa.au/~morris/Year2/plds210/lists.html http://www.nist.gov/dads/HTML/linkedList.html http://developer.gnome.org/doc/API/glib-doubly-linked-lists.html http://developer.gnome.org/doc/API/glib-singly-linked-lists.html
|
Linked Lists. According to this definition, we could have our record hold and
store any information. However, there is one disadvantage each record must
be an instance of the same structure. Furthermore, means that we couldn't have a
record with a char pointing to another structure holding a short, a character
array, and a long. Therefore, they have to be instances of the same structure
for this to work. What is great about each structure is that it can be located
anywhere in memory. Moreover, each node does not have to be linear in memory.
e
end. We could use it as a priority list where the oldest objects get a higher
precedence until deleted from the list. Also, we could also use it as a master
listing of items that need to be kept track of at one time, deleting object when
they need to be, without using any precedence scheme. Furthermore, here's some
code that will add a node onto the end of the list, and then move the end
pointer so that it really does point at the end. Here we add a node onto the end
of our list, then move the Tail pointer to point to the new instance. After this
function we can always access our new node through Tail since we allocated a new
instance, then made Tail point to it!