2.2.2 Pointer Implementation of Lists

Next: 2.2.3 Doubly Linked List Implementation Up: 2.2 Implementation of Lists Previous: 2.2.1 Array Implementation of Lists

In the array implementation,

1.
we are constrained to use contiguous space in the memory
2.
Insertion, deletion entail shifting the elements
Pointers overcome the above limitations at the cost of extra space for pointers.
Singly Linked List Implementation
A list a₁, a₂,..., a_n is organized as shown in Figure 2.1

Figure 2.1: A singly linked list
$\begin{figure} \centerline{\psfig{figure=figures/Fsllist.ps}} \end{figure}$
Let us follow a convention that position i is a pointer to the cell holding the pointer to the cell containing a_i, (for i = 1, 2,..., n). Thus,
- Position 1 is a pointer to the header
- End (L) is a pointer to the last cell of list L
If position of a_i is simply a pointer to the cell holding a_i, then
- Position 1 will be the address in the header
- end (L) will be a null pointer
Insert (x, p, L) : See Figure 2.2
Delete (x, L) : See Figure 2.3

**Figure 2.1:** A singly linked list
$\begin{figure} \centerline{\psfig{figure=figures/Fsllist.ps}} \end{figure}$

**Figure 2.2:** Insertion in a singly linked list
$\begin{figure} \centerline{\psfig{figure=figures/Finssllist.ps}} \end{figure}$

**Figure 2.3:** Deletion in a singly linked list
$\begin{figure} \centerline{\psfig{figure=figures/Fdelsllist.ps}} \end{figure}$

Next: 2.2.3 Doubly Linked List Implementation Up: 2.2 Implementation of Lists Previous: 2.2.1 Array Implementation of Lists

eEL,CSA_Dept,IISc,Bangalore