Data Structures

Home   Index

Linked List

A linked list is a data structure whose elements are arranged in a linear order. Unlike an array, whose order is determined by the array indices, a linked list’s order is determined by a pointer in its elements.
A linked list is basically made up of two object classes. The first is the linked list itself and the other is the elements within the list. An element contains a key to identify the element and a pointer to the next element object within the list. This is known as a singly linked list. A doubly linked list has another pointer in the element pointing to the previous element object within the list.
When creating a linked list, it is important to keep track of the beginning element of the list, especially if it is a singly linked list. When searching a linked list, start at the head of the list and compare its key value to that of the key you are searching for. If it is not the correct value, follow the pointer to the next element and repeat the process until you have found the key or reached the end of the list.
An element is typically inserted into the beginning of a linked list. The new element points to the head of the linked list, thereby becoming the head of the list. When deleting an element from a linked list, a search is done for that element. The previous element will then point to the element that the element to be deleted is pointing to. This effectively removes the element from the list as it is no longer referenced.
A sorted link list is a list whose order follows the order of the keys of the elements contained. A circular list is a list whose end element links to its head. This is sometimes done with a sentinel or dummy element in order to make code clearer and easier to read, but does not have any real effect on the time complexity of searches, deletes and insertions. It is not always done as the extra dummy element may be expensive in the amount of space taken when many small linked lists are involved.

Java example of a doubly linked list

Element Class

import java.lang.String;
import java.lang.Boolean;

public class Link
{
    private Link _previous;
    private Link _next;
    private String _value;
    private String _key;
    
    public String GetValue()
    {
        return this._value;
    }

    public void SetValue(String value)
    {
        this._value = value;
    }
    
    public String GetKey()
    {
        return this._key;
    }

    public void SetKey(String key)
    {
        this._key = key;
    }
    
    public Link GetPrevious()
    {
        return this._previous;
    }

    public void SetPrevious(Link previous)
    {
        this._previous = previous;
    }
    
    public Link GetNext()
    {
        return this._next;
    }

    public void SetNext(Link next)
    {
        this._next = next;
    }
}

Linked List Class

import java.lang.String;
import java.lang.Boolean;

public class LinkList
{
    private Link _starter;
    private Link _current;
    
    public void Insert(String key, String value)
    {
        this._current = new Link();
        this._current.SetNext(this._starter);
        if (this._starter != null) this._starter.SetPrevious(this._current);
        this._current.SetKey(key);
        this._current.SetValue(value);
        this._starter = this._current;
    }
    
    public String GetValue(String key)
    {
        this.SetCurrent(key);
        if (this._current != null) return this._current.GetValue();
        return null;
    }
    
    private void SetCurrent(String key)
    {
        this._current = this._starter;
        while (this._current != null && this._current.GetKey() != key)
        {
            this._current = this._current.GetNext();
        }
    }
    
    public Boolean Delete(String key)
    {
        this.SetCurrent(key);
        if (this._current != null)
        {
            if (this._current.GetNext() == null)
            {
                if (this._current.GetPrevious() != null)
                {
                    this._current.GetPrevious().SetNext(null);
                }
                else
                {
                    this._starter = null;
                }
            }
            else if (this._current.GetPrevious() == null)
            {
                this._current.GetNext().SetPrevious(null);
                this._starter = this._current.GetNext();
            }
            else
            {
                this._current.GetNext().SetPrevious(this._current.GetPrevious());
                this._current.GetPrevious().SetNext(this._current.GetNext());
            }
            return true;
        }
        return false;
    }
    
    public String ToString()
    {
        String elements = "The elements in this linked list are [";
        this._current = this._starter;
        while (this._current != null)
        {
            if (this._current != this._starter) elements += ", ";
            elements += "[" + this._current.GetKey() + "," + this._current.GetValue() + "]";
            this._current = this._current.GetNext();
        }
        elements += "]";
        return elements;
    }
}
Previous   Next