In this Post, the list data structure is presented. This structure can be used as the basis for the implementation of other data structures (stacks, queues etc.). The basic linked list can be used without modification in many programs.
However, some applications require enhancements to the linked list design. These enhancements fall into three broad categories and yield variations on linked lists that can be used in any combination: circular linked lists, double
linked lists and lists with header nodes
Basic Concept of Linked Lists
Linked lists and arrays are similar since they both store collections of data. Array is the most common data structure used to store collections of elements. Arrays are convenient to declare and provide the easy syntax to access any element by its index number. Once the array is set up, access to any element is convenient and fast. The disadvantages of arrays are:
- The size of the array is fixed. Most often this size is specified at compile time. This makes the programmers to allocate arrays, which seems “large enough” than required
- Inserting new elements at the front is potentially expensive because existing elements need to be shifted over to make room.
- Deleting an element from an array is not possible.
Linked lists have their own strengths and weaknesses, but they happen to be strong where arrays are weak. Generally array’s allocates the memory for all its elements in one block whereas linked lists use an entirely different strategy. Linked lists allocate memory for each element separately and only when necessary.
Here is a quick review of the terminology and rules of pointers. The linked list code will depend on the following functions:
malloc() is a system function which allocates a block of memory in the “heap” and returns a pointer to the new block. The prototype of malloc() and other heap functions are in stdlib.h. malloc() returns NULL if it cannot fulfill the request. It is defined by:
void *malloc (number_of_bytes)
Since a void * is returned the C standard states that this pointer can be converted to any type. For example,
char *cp; cp = (char *) malloc (100);
Attempts to get 100 bytes and assigns the starting address to cp. We can also use the sizeof() function to specify the number of bytes. For example,
int *ip; ip = (int *) malloc (100*sizeof(int));
free() is the opposite of malloc(), which de-allocates memory. The argument to free() is a pointer to a block of memory in the heap — a pointer which was obtained by a malloc() function. The syntax is:
The advantage of free() is simply memory management when we no longer need a block.