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:
free (ptr);
The advantage of free() is simply memory management when we no longer need a
block.
3.1. Linked List Concepts:
A linked list is a non-sequential collection of data items. It is a dynamic data structure.
For every data item in a linked list, there is an associated pointer that would give the
memory location of the next data item in the linked list.
The data items in the linked list are not in consecutive memory locations. They may be
anywhere, but the accessing of these data items is easier as each data item contains
the address of the next data item.
Advantages of linked lists:
Linked lists have many advantages. Some of the very important advantages are:
1. Linked lists are dynamic data structures. i.e., they can grow or shrink during
the execution of a program.
2. Linked lists have efficient memory utilization. Here, memory is not pre-
allocated. Memory is allocated whenever it is required and it is de-allocated
(removed) when it is no longer needed.
3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility
in inserting a data item at a specified position and deletion of the data item
from the given position.
4. Many complex applications can be easily carried out with linked lists.
Disadvantages of linked lists:
1. It consumes more space because every node requires a additional pointer to
store address of the next node.
2. Searching a particular element in list is difficult and also time consuming.
3.2. Types of Linked Lists:
Basically we can put linked lists into the following four items:
1. Single Linked List.
2. Double Linked List.
3. Circular Linked List.
4. Circular Double Linked List.
A single linked list is one in which all nodes are linked together in some sequential
manner. Hence, it is also called as linear linked list.
,A double linked list is one in which all nodes are linked together by multiple links which
helps in accessing both the successor node (next node) and predecessor node (previous
node) from any arbitrary node within the list. Therefore each node in a double linked
list has two link fields (pointers) to point to the left node (previous) and the right node
(next). This helps to traverse in forward direction and backward direction.
A circular linked list is one, which has no beginning and no end. A single linked list can
be made a circular linked list by simply storing address of the very first node in the link
field of the last node.
A circular double linked list is one, which has both the successor pointer and
predecessor pointer in the circular manner.
Comparison between array and linked list:
ARRAY LINKED LIST
Size of an array is fixed Size of a list is not fixed
Memory is allocated from stack Memory is allocated from heap
It is necessary to specify the number of It is not necessary to specify the
elements during declaration (i.e., during number of elements during declaration
compile time). (i.e., memory is allocated during run
time).
It occupies less memory than a linked It occupies more memory.
list for the same number of elements.
Inserting new elements at the front is Inserting a new element at any position
potentially expensive because existing can be carried out easily.
elements need to be shifted over to
make room.
Deleting an element from an array is Deleting an element is possible.
not possible.
Trade offs between linked lists and arrays:
FEATURE ARRAYS LINKED LISTS
Sequential access efficient efficient
Random access efficient inefficient
Resigning inefficient efficient
Element rearranging inefficient efficient
Overhead per elements none 1 or 2 links
, Applications of linked list:
1. Linked lists are used to represent and manipulate polynomial. Polynomials are
expression containing terms with non zero coefficient and exponents. For
example:
P(x) = a0 Xn + a1 Xn-1 n-1 X + an
2. Represent very large numbers and operations of the large number such
as addition, multiplication and division.
3. Linked lists are to implement stack, queue, trees and graphs.
4. Implement the symbol table in compiler construction
3.3. Single Linked List:
A linked list allocates space for each element separately in its own block of memory
called a "node". The list gets an overall structure by using pointers to connect all its
nodes together like the links in a chain. Each node contains two fields; a "data" field to
store whatever element, and a "next" field which is a pointer used to link to the next
node. Each node is allocated in the heap using malloc(), so the node memory continues
to exist until it is explicitly de-allocated using free(). The front of the list is a pointer to
.
A single linked list is shown in figure 3.2.1.
HEAP
10 200 20 300 30 400 40 X
100 200 400
The start
pointer holds
Stores the next
the address the data. node address. The next field of the
of the first last node is NULL.
node of the
list.
Figure 3.2.1. Single Linked List
The beginning of the linked list is stored in a "start" pointer which points to the first
node. The first node contains a pointer to the second node. The second node contains a
pointer to the third node, ... and so on. The last node in the list has its next field set to
NULL to mark the end of the list. Code can access any node in the list by starting at the
start and following the next pointers.
The start pointer is an ordinary local pointer variable, so it is drawn separately on the
left top to show that it is in the stack. The list nodes are drawn on the right to show
that they are allocated in the heap.
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:
free (ptr);
The advantage of free() is simply memory management when we no longer need a
block.
3.1. Linked List Concepts:
A linked list is a non-sequential collection of data items. It is a dynamic data structure.
For every data item in a linked list, there is an associated pointer that would give the
memory location of the next data item in the linked list.
The data items in the linked list are not in consecutive memory locations. They may be
anywhere, but the accessing of these data items is easier as each data item contains
the address of the next data item.
Advantages of linked lists:
Linked lists have many advantages. Some of the very important advantages are:
1. Linked lists are dynamic data structures. i.e., they can grow or shrink during
the execution of a program.
2. Linked lists have efficient memory utilization. Here, memory is not pre-
allocated. Memory is allocated whenever it is required and it is de-allocated
(removed) when it is no longer needed.
3. Insertion and Deletions are easier and efficient. Linked lists provide flexibility
in inserting a data item at a specified position and deletion of the data item
from the given position.
4. Many complex applications can be easily carried out with linked lists.
Disadvantages of linked lists:
1. It consumes more space because every node requires a additional pointer to
store address of the next node.
2. Searching a particular element in list is difficult and also time consuming.
3.2. Types of Linked Lists:
Basically we can put linked lists into the following four items:
1. Single Linked List.
2. Double Linked List.
3. Circular Linked List.
4. Circular Double Linked List.
A single linked list is one in which all nodes are linked together in some sequential
manner. Hence, it is also called as linear linked list.
,A double linked list is one in which all nodes are linked together by multiple links which
helps in accessing both the successor node (next node) and predecessor node (previous
node) from any arbitrary node within the list. Therefore each node in a double linked
list has two link fields (pointers) to point to the left node (previous) and the right node
(next). This helps to traverse in forward direction and backward direction.
A circular linked list is one, which has no beginning and no end. A single linked list can
be made a circular linked list by simply storing address of the very first node in the link
field of the last node.
A circular double linked list is one, which has both the successor pointer and
predecessor pointer in the circular manner.
Comparison between array and linked list:
ARRAY LINKED LIST
Size of an array is fixed Size of a list is not fixed
Memory is allocated from stack Memory is allocated from heap
It is necessary to specify the number of It is not necessary to specify the
elements during declaration (i.e., during number of elements during declaration
compile time). (i.e., memory is allocated during run
time).
It occupies less memory than a linked It occupies more memory.
list for the same number of elements.
Inserting new elements at the front is Inserting a new element at any position
potentially expensive because existing can be carried out easily.
elements need to be shifted over to
make room.
Deleting an element from an array is Deleting an element is possible.
not possible.
Trade offs between linked lists and arrays:
FEATURE ARRAYS LINKED LISTS
Sequential access efficient efficient
Random access efficient inefficient
Resigning inefficient efficient
Element rearranging inefficient efficient
Overhead per elements none 1 or 2 links
, Applications of linked list:
1. Linked lists are used to represent and manipulate polynomial. Polynomials are
expression containing terms with non zero coefficient and exponents. For
example:
P(x) = a0 Xn + a1 Xn-1 n-1 X + an
2. Represent very large numbers and operations of the large number such
as addition, multiplication and division.
3. Linked lists are to implement stack, queue, trees and graphs.
4. Implement the symbol table in compiler construction
3.3. Single Linked List:
A linked list allocates space for each element separately in its own block of memory
called a "node". The list gets an overall structure by using pointers to connect all its
nodes together like the links in a chain. Each node contains two fields; a "data" field to
store whatever element, and a "next" field which is a pointer used to link to the next
node. Each node is allocated in the heap using malloc(), so the node memory continues
to exist until it is explicitly de-allocated using free(). The front of the list is a pointer to
.
A single linked list is shown in figure 3.2.1.
HEAP
10 200 20 300 30 400 40 X
100 200 400
The start
pointer holds
Stores the next
the address the data. node address. The next field of the
of the first last node is NULL.
node of the
list.
Figure 3.2.1. Single Linked List
The beginning of the linked list is stored in a "start" pointer which points to the first
node. The first node contains a pointer to the second node. The second node contains a
pointer to the third node, ... and so on. The last node in the list has its next field set to
NULL to mark the end of the list. Code can access any node in the list by starting at the
start and following the next pointers.
The start pointer is an ordinary local pointer variable, so it is drawn separately on the
left top to show that it is in the stack. The list nodes are drawn on the right to show
that they are allocated in the heap.
