The Linked List Abstract Data

Introduction

Abstract data types enable us to create user defined objects that have properties and methods that are distinct from their implementation. It is a concept at the core of object oriented programming allowing for:

• Object Re-use
• Ease of maintenance
• Neutrality of implementation

A linked list is simply a self-organizing storage container. Data of any type may be stored in each node, and each node is connected to at least one other. The two common types are singly and doubly linked lists, which are covered in a later article.

Linked List Data Type

A linked list abstract data type usually has two components. The first is a list management, or container, component. It needs to contain references to the first (and possibly last) node in the list, as well as the node that is currently 'in focus'.

The second component is the data node. Each linked list contains a collection of nodes that are connected together - they refer to each other. Rather than containing a collection of references - one to each node - the list container simply has to contain a reference to the first node, commonly known as the head.

Allocating the DataContent will vary from one language to another. The C language, for example, allows the use of a pointer known as void which can be cast into any data type. Most implementations will store DataContent as a reference to another user define object; probably an abstract data type itself.

Linked List Methods

The linked list abstract data type needs methods to set up the container, add, remove and access nodes, as well as ways to traverse the list. This list traversal can take several forms, but the most common is to provide a way to return the reference to the first node, and then follow the chain until the mast node, at which point an end of list value should be returned.

The container needs also to be able to destroy itself, and remove the nodes associated with it. With these methods defined, we need no longer worry about how the node will manage itself, and can concentrate on making use of it.

One note is that DeleteNode should delete the node currently in focus. AddNode might add the node top the start, end, or insert the node in the case of a sorted linked list. Each node contains methods allowing the node to manage its own properties, including a reference to neck node in the linked list.

The DestroyNode is described later on, as it is a special case. The other methods should be fairly self-explanatory. It is assumed that when the ListNode is destroyed, it cleans up after itself by releasing its DataContent.

Using The Singly Linked List

Typically, this is a multipart operation. First, we set up an abstract data type, complete with the required functions for it's management, which represents the daya we want to store. Then, we can pass that to the ListNode during a call to SetData.

We can then invoke the creation of a LinkedList container, and use GetFirst to ensure that it is empty. Provided that it is, we can proceed to create a ListNode, set the data with SetData, and add it to the list with a call to AddNode, using a reference to the newly create data object.

Traversing the list requires calls to GetFirst and GetNext, testing the return values appropriately:

We can also delete the node that is in focus, by first checking that it is the correct one, and then deleting it:

Finally, we can destroy the list with a simple call to DestroyList. A common way to implement the DestroyList and DestroyNode methods is as a recursive call:

Before each node self-destructs, it calls the destruction of the node that follows it. This carries on down the chain until the final node finds no more after itself, and the function returns. This approach is quite heavy on calling stack space, but a better implementation is left as an exercise for the reader.

Print Article

Email Article

View All Articles

How to subscribe to feeds