Singly Linked List Using Arrays

My Singly Linked List Article is a direct implementation of Singly Linked List, where the memory allocation of more Nodes is done only when necessary. However, in reality, the computer memory is a contiguous array of memory locations. We can emulate the memory management of a Singly Linked List using Arrays.

The amusing part of this implementation is deleting a Node. Instead of deallocating it, another Singly List should handle a set of deleted Nodes. This implementation is also faster than the regular Singly Linked List implementation as allocation is done during initialization.

In this article, I will show how you can implement two Singly Linked List sharing one Single Array. The first set contains the Singly Linked List and the second is the Deleted Singly Linked List.

Again, due to convenience, we will implement this using C++.

We start off by declaring our Singly List Array class (SLA).

template<class T>
class SLA
{
private:
	int  maxListElements;
	int* next;
	T*	 data;

	int	 head, tail, detached, available;

public:
	SLA(int max);
	~SLA();

	inline int insertAfter(int node, T value);
	inline void deleteAfter(int node);

	void display();

	inline int getHead() const { return head; }
	inline int getTail() const { return tail; }
	inline int getDetachedHead() const { return detached; }
};

Our implementation of Single List Array (SLA) consists of the following operations:

1. Initialization (Constructor)

   The initialization takes the number (max) of Nodes to pre-allocate in an Array. The initialization begins by allocating an Array of Data of type T with size max + 3 and an Array of Next Node Reference of type Integer with size max + 3.

   template<class T>
   SLA<T>::SLA(int max) 
   	: 
   	data(new T[max+3]),
   	next(new int[max+3])
   {
   	head = 0;
   	tail = 1;
   	detached = 2;
   	available = 2;
   	maxListElements = max+3;
   
   	next[head] = tail;
   	next[tail] = tail;
   	next[detached] = 3;
   
   	//
   	// Set 3 to max - 1 as detached to avoid conditionals in addAfter
   	// purposely set detached values to negative to see the difference
   	// 
   	int maxListElementsLess1 = maxListElements - 1;
   	for (int i = 3; i < maxListElementsLess1; ++i)
   	{
   		next[i] = i + 1;
   		data[i] = -i + 2;
   	}
   	next[maxListElementsLess1] = tail;
   	data[maxListElementsLess1] = -maxListElementsLess1 + 2;
   }
   

   The Head, Tail, and Detached Head are set to arrays next[0], [1], and [2] respectively, and all of them except for the Detached Header are pointed to the Tail. The data of these Nodes are left untouched.

   It is important to take note and to avoid the necessary conditional statements inside the Insert After method, that we need to initialize the rest of the elements of the Node Array as detached. To do this, we set the Detached Head to point to next[3], then starting from next[3] to next[max - 2], set the next Node Reference to the i + 1, where i is the index starting from 3. At the end of it all, we set the last element to point to the Tail Node.

   As you've noticed in the script above, we initially set the data to negative. This is just to give a distinction between the regular Singly Linked List and Detached Singly Linked List when displayed.

2. Destructor

   Our destructor would be simply to delete the two arrays we've preallocated.

   template<class T>
   SLA<T>::~SLA()
   {
   	delete next;
   	delete data;
   }
   

    

3. Insert After (insertAfter)

   Since we've initialized the Detached Nodes, we can always get from our list of Detached Nodes. Otherwise, a conditional statement to check whether next[detached] is equal to tail is necessary and this approach requires the "available" variable to monitor the next available slot in the Array.

   template<class T>
   int SLA<T>::insertAfter(int node, T value)
   {
   	//
   	// Prevent this conditional statement by initializing 
   	// next[3] to next[max - 1] as detached;
   	//
   
   	// int t;
   	//
   	// if (next[detached] == tail)
   	// {
   	// 	 t = ++available;
   	// }
   	// else
   	// {
   	// 	 t = next[detached];
   	//
   	//	 // detach from detached list 
   	//	 next[detached] = next[next[detached]];
   	// }
   
   	int t = next[detached];
   	next[detached] = next[next[detached]];
   
   	data[t] = value;
   	next[t] = next[node];
   	next[node] = t;
   
   	return t;
   }
   

   The inserAfter method starts by assigning the Node Reference of the next Node pointed to by next[detached] to a temporary variable. The next[detached] is then assigned the next Node Reference of the next Node Reference of the detached next[next[detached]].

   The succeeding script is the normal Singly Linked List Insert After procedure. 

   It is important to take note that it is the programmer's responsibility to check whether insertAfter method exceeds the maximum allocated space. The validation should be not in the scope of this class to gain that extra precious speed.

4. Delete After (deleteAfter)

   Our deleteAfter method simply references the next[node] to the next Node Reference after the next Node Reference next[next[node]].

   template<class T>
   void SLA<T>::deleteAfter(int node)
   {
   	// Add after to free
   	int t = next[node];	
   
   	// Delete 
   	next[node] = next[next[node]];
   	next[t] = next[detached];
   	next[detached] = t;
   }
   

   deleteAfter doesn't have the delete temporary variable but rather it is replaced a script to set the next Node Reference of the Detached Node next[detached] to the initial next[node].

5. Display

   Our display method a simple walk-the-list procedure to demonstrate the display of the Nodes under the Regular Singly Linked List and the Detached Singly Linked List.

   template<class T>
   void SLA<T>::display()
   {
   	int t = head;
   	std::cout << "List:\n";
   	while (next[t] != tail)
   	{
   		std::cout << data[next[t]] << "\n";
   		t = next[t];
   	}
   
   	t = detached;
   	std::cout << "\nDetached List:\n";
   	while (next[t] != tail)
   	{
   		std::cout << data[next[t]] << "\n";
   		t = next[t];
   	}
   
   }
   

    

So there you go, the full demonstration and implementation of Singly Linked List using Arrays. This implementation is necessary if your application requires a Singly Linked List and speed is preferred over space.

Download and try to tweak the full Singly Linked Array class for yourself below.