Linked Lists:
Linked lists are a type of data structure for storing information as a list. They are a memory efficient alternative to arrays because the size of the list is only ever as large as the data. Plus they do not have to shift data and recopy when resizing as dynamic arrays do.
They do have the extra overhead of 1 or 2 pointers per data node, so they make sense only with larger records. You would not want to store a list of integers in a linked list because it would actually double your memory overhead over the same list in an array.
There are three different types of linked lists, but the other two are just variations of the basic singly linked list. If you understand this linked list then you will be able to handle other two types of lists.
Advantages of Linked Lists:
A linked list is a dynamic data structure and therefore the size of the linked list can grow or shrink in size during execution of the program. A linked list does not require any extra space therefore it does not waste extra memory. It provides flexibility in rearranging the items efficiently.The limitation of linked list is that it consumes extra space when compared to a array since each node must also contain the address of the next item in the list to search for a single item in a linked list is cumbersome and time consuming process.
Linked lists Types:
There are 4 different kinds of linked lists:- Linear singly linked list
- Circular singly linked list
- Two way or doubly linked list
- Circular doubly linked list.
Linked List Nodes:
A linked list gets their name from the fact that each list node is "linked" by a pointer. A linked list node is comparable to an array element. A node contains a data portion and a pointer portion, and is declared as structs in C.As an example, we can implement a list of high scores for a game as a linked list.
Creating Linked Lists:
A linked list always has a base node that is most commonly called a head, but some call it as a root. An empty linked list will have this node and will be set to NULL. This goes for all three types of linked lists. The last node in a linked list always points to NULL.Let us declare our linked list for implementing high scores list.
struct llnode *head = NULL;
Here we just declared a regular pointer variable of the node struct we declared, and then set the head to NULL to indicate the list is empty.
Traversing a Linked List:
Moving through a linked list and visiting all the nodes is called traversing the linked list. There is more than one way to encounter segmentation faults when traversing a linked list, but if you are careful and follow 2 basic checks you will be able to handle segmentation faults.To traverse a singly linked list you create a pointer and set it to head. Often called the current node as a reminder that it is keeping track of the current node. Always make sure to check that head is not NULL before trying to traverse the list or you will get a segmentation fault. You may also need to check that the next pointer of the current node is not NULL, if not, you will go past the end of the list and create a segmentation fault.
C Doubly Linked Lists:
Doubly linked lists are the same as singly linked lists, except they have an extra pointer per node so they point to the next node and the previous node. You just make sure that whenever you insert a node you set next to the next node and previous to the previous node. They will also commonly keep a tail and head pointer so that traversal may start at either end of the list.
Doubly Linked List Nodes
A doubly linked list node would look like this:struct dllnode {
Arbitrary Data Portion
struct dllnode *next;
struct dllnode *previous;
};
It contains a data portion and a pointer to both the next and previous nodes in the list sequence allowing for two-way traversal.
Creating A Doubly Linked List:
When creating a doubly linked list, we want to be able to go both ways as well as be able to start at either end of the list when traversing it. As mentioned earlier, we use a both a tail and a head pointer to provide this functionality.Checking for head being NULL is sufficient for checking for an empty list.
if (head == NULL) {
//This node becomes the first and last node in the list.
newnode->previous = NULL;
newnode->next = NULL;
head = newnode;
tail = head;
}
Pretty much the same as we have done throughout this tutorial with the singularly linked lists, with the addition of the previous pointer needing to be set to NULL and the tail also being equal to the new node.
Inserting Nodes:
Same as linear singularly linked lists, we can add at the beginning, middle, or end of a doubly linked list.Placing a node at the beginning of a doubly linked list is quite simple but an empty and nonempty must be handled differently.
When the list is empty all you have to do is create the new node, set its next and previous pointers to NULL, and point the head and tail pointers to it. We already saw the code for this in the last section.
Inserting a new node at the beginning of a nonempty doubly linked list is a little tricky, but not impossible. First you create your new node and set its previous pointer to NULL, but the next pointer to the current head. Then set the current head's previous pointer to the new node being inserted to move the old head one up in the list. Now all you have to do is point head at the new node and you are done.
In code it should look something like this
newnode->previous = NULL;
newnode->next = head;
head->previous = newnode;
head = newnode; Insertion of a new node at the end of the list is quite similar although we use the tail pointer as a reference instead of the head pointer. Since the empty list case here is identical to the empty list case above for insert at beginning we will skip it.
To place a node at the end of the nonempty list you create the new node, set its next pointer to NULL and its previous pointer to the current tail. Then set the current tail's next pointer to the new node. Now point tail to the new node which you have inserted a node at the back of the list. Although it's not in our example, here is a code snippet
newnode->next = NULL;
newnode->previous = tail;
tail->next = newnode;
tail = newnode;
Here's the fun part, this is the greatest feature of the doubly linked list. It's actually so simple though, you may be disappointed.
Forward traversal is identical to singly linked list traversal. Seriously, there is no difference. This should look familiar.
if (head != NULL) {
currentnode = head;
while (currentnode->next != NULL) {
currentnode = currentnode->next;
}
}
With that in mind, you would think that going the other way would be the same but with the tail pointer. You would be correct.
In this tutorial you will learn about C Programming - What is Circular Linked List, Adding Nodes to Circular Linked Lists, Traversing a Circularly Linked List and working with Circularly Linked List Example.
Circular linked lists are usually used for a queue or stack type situation, or for implementing a round robin algorithm in system level programming. You could also use one for a multiplayer game where you were keeping track of player's turns where it just repeats until the game ends.
They are exactly the same as a singly linked list, but instead of setting the next pointer in the last node of the list to NULL, you set it to point to head. Hence the name circular. Instead of a head pointer, they commonly use a tail pointer instead to keep track of the last node.
A cingularly linked list node looks exactly the same as a linear singly linked list. Here's the node for the example.
if (tail != NULL) {
currentnode = tail;
while (currentnode->previous != NULL) {
currentnode = currentnode->previous;
}
}
C Circular Linked Lists:
In this tutorial you will learn about C Programming - What is Circular Linked List, Adding Nodes to Circular Linked Lists, Traversing a Circularly Linked List and working with Circularly Linked List Example.
Circular linked lists are usually used for a queue or stack type situation, or for implementing a round robin algorithm in system level programming. You could also use one for a multiplayer game where you were keeping track of player's turns where it just repeats until the game ends.
They are exactly the same as a singly linked list, but instead of setting the next pointer in the last node of the list to NULL, you set it to point to head. Hence the name circular. Instead of a head pointer, they commonly use a tail pointer instead to keep track of the last node.
A cingularly linked list node looks exactly the same as a linear singly linked list. Here's the node for the example.
struct cllnode {
char name[4];
struct cllnode *next;
};
It should be familiar from the previously introduced linear linked list, just a data portion and the next pointer.
Just as in the singularly linked list case you first check if the list pointer (no matter what you are calling it) is NULL. Then set the tail equal to the new node being added and make its pointer point back at itself, thus completing the circle.
When there are nodes in the list, you first set the new node's next pointer to tail->next because you are adding it just after tail, not at tail. You may be able to see why we use tail pointers rather than head pointers for circularly linked lists. The head would be 2 pointers away from where we perform insertions.
After that, you set tail's next pointer to the new node and set tail equal to the new node. Viola, we have inserted a new node at the end of the list, and tail is now pointing at it.
As we see in this snippet of our example program, it's not any more difficult to traverse, it's just different
We begin with the familiar check for the list's existence. If we have
a list, we set the current pointer to the node after tail. From here we
can just go through the nodes until we return to tail, so we use a
while loop to do that. The traversal is the same as before in that you
just set the current pointer to the next one at the end of the wile
loop.
Now if you want to do something when you get to the tail you must do it after the while loop traversal, because our condition stopped the traversal at the node just before tail and started just after it. As you can see we had to add an addition print out block after the while loop to be able to see the last node's information printed out.
Adding Nodes to Circular Linked Lists
Adding nodes and creating new circularly linked lists is very similar to the linear ones we learned previously. Let's look at our example to illustrate.
void addNode(struct cllnode *newnode) {
//List is empty. Create new list.
if (tail == NULL) {
tail = newnode;
newnode->next = tail;
} else {
//List isn't empty so add at the tail. Remember "first in first out."
newnode->next = tail->next;
tail->next = newnode;
tail = newnode;
}
}
That addNode function is all it takes to handle both the empty and
non-empty singularly linked list cases when adding new nodes. You add at
the back of the list in this linked list case and that's one of the
reasons these are used for modeling queues and FIFO stacks. Just as in the singularly linked list case you first check if the list pointer (no matter what you are calling it) is NULL. Then set the tail equal to the new node being added and make its pointer point back at itself, thus completing the circle.
When there are nodes in the list, you first set the new node's next pointer to tail->next because you are adding it just after tail, not at tail. You may be able to see why we use tail pointers rather than head pointers for circularly linked lists. The head would be 2 pointers away from where we perform insertions.
After that, you set tail's next pointer to the new node and set tail equal to the new node. Viola, we have inserted a new node at the end of the list, and tail is now pointing at it.
Traversing a Circularly Linked List:
Traversing a circularly linked list is a little different than the regular type, due to the fact that there is no NULL termination to tell you when to stop. However, we can just use the tail pointer for this purpose as well.As we see in this snippet of our example program, it's not any more difficult to traverse, it's just different
if (tail != NULL) {
current = tail->next;
while (current != tail) {
...
current = current->next;
}
current = tail;
...
}
Now if you want to do something when you get to the tail you must do it after the while loop traversal, because our condition stopped the traversal at the node just before tail and started just after it. As you can see we had to add an addition print out block after the while loop to be able to see the last node's information printed out.
No comments:
Post a Comment