# The blog ofJonathan Pepin

2014-01-11

A linked list is a data structure in which elements are arranged in linear order (like an array).
But unlike an array, where the order is determined by the index of each element in it, the order in a Linked List is determined by a pointer (or multiple ones) in each element of the list.

There are multiple types on Linked List, but here, I'll use a Doubly Linked List.

In a Doubly Linked List L, each element has 3 attributes;

• key, which represents the data,
• next, a pointer to its successor, and
• prev, pointing to its predecessor.

For an element E, `E.prev == nil` means E is the list's head. The first element in the list. On the contrary, `E.next == nil` means E is the tail. The last element of the list.

Here is what an Element would look like:

``````class Element
attr_accessor :key, :prev, :next

def initialize(args)
@key = args[:key]
@next = args[:nex]
@prev = args[:prev]
end
end
``````

And here are 2 elements, one being the head.
As you can see, `head.next` points to tail and `tail.prev` points to head.

``````head = Element.new key: 13
tail = Element.new key: 25, prev: head
``````

This is a really simple implementation of Element. Here I create the element and link them manually.

Our list needs its own class to implement basic operations such as

• `insert` to add an element (element becomes the new head)
• `delete` to remove en element
• `search` to look for an element
• `minimum` and `maximum` to find the smallest and biggest element

Here would be an implementation of that class:

``````class LinkedList

def initialize(element=nil)
end
end

=> #<Element:0x007f878aafc198 @key=13, @next=nil, @prev=nil>
``````

The list is initialized with an element which becomes the head (and the tail being the only element). The element can be nil, in which case the list would be empty.

Now let's create the `insert` method, to allow us to add new elements to the list:

``````def insert(element)
end
``````

So what exactly is happening here?

1. The new element's next attribute is set to point to the list's current head (insert adds elements in front of the list, remember?),
2. list head's prev is set to point to our element, and
3. our list's `@head` is set to our new element.

As you can see, in this example we had a linked list where the head is 9. We `insert`ed the element with `key: 25`, which becomes the new head.

On the opposite, let's now implement `delete`, which will allow us to remove an element from our list:

``````def delete(element)
el.prev ? el.prev.next = el.next : @head = el.next
el.next.prev = el.prev if el.next
end
``````
1. On line 1, we check if the element has a predecessor by checking if its `.prev` exists. If it does, we set its predecessor `.next` to point to our element's successor. If our element doesn't have a predecessor, it means it's our list head. In that case, we set the head to point to its successor.
2. Then, we do the exact opposite; Unless our element is the tail, we set its successor to point to its predecessor.

As you can see, in this example we removed 4. Hence, `16.next` now points to 1 and `1.prev` points to 16. No more 4.

Finally, let's implement `search`, allowing us to find an element from a key in the list (makes more sense to look for a key than an element).
If the element we are looking for is not in the list, we will return `nil`:

``````def search(key)
while x && x.key != key
x = x.next
return x
end
``````

Here the search works like a sequential search. It starts from the head, it iterates over every element until it finds an element with the key we are looking for.
If no element has the key we are looking for, it will iterate until the last element of our list, which has `.next == nil`, which will be returned.

Here. I'm done with Linked List.

This is obviously a really simple implementation in ruby, which I do for learning purposes.