Application of linked list concepts are useful to model many different abstract data types such as queues, stacks and trees. If we restrict the process of insertion to one end of the list and deletions to the other end, then we have a model of a queue. That is, we can insert an item at the rear and remove an item at the front (see Fig). This obeys the discipline of “first in, first out” (FIFO). There are many examples of queues in real life applications.
If we restrict insertions and deletions to occur only at the beginning of list, then we model another data structure known as stack. Stacks are also referred to as push down lists. An example of a stack is the “n” tray of a busy executive. The files pile up in the tray, and whenever the executive has time to clear the files, he takes it off from the top. That is, files are added at the top and removed from the top. Stacks are sometimes referred to as “last in, first out” (LIFO) structure.
Lists, queues and stacks are all inherently one dimensional. A tree represents a two dimensional application linked list. Trees are frequently encountered in everyday life. One example is the organizational chart of a large company. Another example is the chart of sports tournaments.
Just Remember – Application of Linked List
- Use the sizeof operator to determine the size of a linked list.
- When using memory allocation functions malloc and calloc, test for a NULL pointer return value. Print appropriate message if the memory allocation fails.
- Never call memory allocation functions with a zero size.
- Release the dynamically allocated memory when it is no longer required to avoid any possible “memory leak”.
- Using free function to release the memory not allocated dynamically with malloc or calloc is an error.
- It is an error to declare a self-referential structure without a structure tag.
- Using a pointer after its memory has been released is an error.
- It is an error to assign the return value from malloc or calloc to anything other than a pointer.
- It is a logic error to set a pointer to NULL before the node has been released. The node is irretrievably lost.
- Use of a invalid pointer with free may cause problems and, sometimes, system crash.
- It is an error to release individually the elements of an array created with calloc.
- It is a logic error to fail to set the link filed in the last node to null.
| Read More Topics |
| Dynamic memory allocation |
| Pointer to pointer in C++ |
| New and Delete in C++ |
| Functions of Layer in the OSI Model |
