Linked List – Why Linked List Implementation is Considered Linear

Here is something part way between an example and an analogy. You have some errands to do, so you grab a piece of paper and write:

• bank
• groceries
• drop off drycleaning

Then you remember that you also need to buy stamps. Because of the geography of your town, you need to do that after the bank. You could copy your whole list onto a new piece of paper:

• bank
• stamps
• groceries
• drop off drycleaning

or you could scribble on the one you had:

• bank ....... STAMPS
• groceries
• drop off drycleaning

As you thought of other errands, you might write them at the bottom of the list, but with arrows reminding yourself what order to do them in. This is a linked list. It's quicker and easier than copying the whole list around every time you add something.

Then your cell phone rings while you're at the bank "hey, I got the stamps, don't pick up any more". You just cross STAMPS off the list, you don't rewrite a whole new one without STAMPS in it.

Now you could actually implement an errands list in code (maybe an app that puts your errands in order based on your geography) and there's a reasonable chance you would actually use a linked list for that in code. You want to add and remove lots of items, order matters, but you don't want to recopy the whole list after each insertion or deletion.

Here's an implementation that I dug up from when I was dealing with graphs. Although it's in C#, with a few minor adjustments it could compile in Java.

To make it directed you would have to copy v.Adjacents.Add(new Edge(w, cost)); and reverse the direction, thereby taking up double the space.

I don't think it's any better than what you have though.

class Edge
{
    public Vertex Destination { get; set; }
    public double Cost { get; set; }

    public Edge(Vertex destination, double cost)
    {
        Destination = destination;
        Cost = cost;
    }

}

class Vertex
{
    public string Name { get; set; }
    public List<Edge> Adjacents { get; set; }
    public double Distance { get; set; }

    public Vertex(string name)
    {
        Name = name;
        Adjacents = new List<Edge>();
        Distance = double.MaxValue;
    }
}

class Graf
{
    private readonly Dictionary<string, Vertex> vertexmap = new Dictionary<string, Vertex>();

    public void AddEdge(string source, string dest, double cost)
    {
        var v = GetVertex(source);
        var w = GetVertex(dest);
        v.Adjacents.Add(new Edge(w, cost));
    }

    private Vertex GetVertex(string vertexname)
    {
        Vertex v;
        vertexmap.TryGetValue(vertexname, out v);
        if (v == null)
        {
            v = new Vertex(vertexname);
            vertexmap.Add(vertexname, v);
        }
        return v;
    }
}