Data Structures- Linked List
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 head.next = tail
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
insertto add an element (element becomes the new head)
deleteto remove en element
searchto look for an element
maximumto find the smallest and biggest element
Here would be an implementation of that class:
class LinkedList attr_reader :head def initialize(element=nil) @head = element end end head = Element.new key: 13 list = LinkedList.new head list.head => #<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) el.next = @head @head.prev = el if @head @head = el end
So what exactly is happening here?
- 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?),
- list head's prev is set to point to our element, and
- our list's
@headis set to our new element.
As you can see, in this example we had a linked list where the head is 9. We
inserted 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
- On line 1, we check if the element has a predecessor by checking if its
.prevexists. If it does, we set its predecessor
.nextto 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.
- 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
def search(key) x = @head 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.
Other types of linked lists
- Singly Linked Lists are linked lists where nodes have only one pointer, to its successor.
- Sorted Linked Lists's linear order corresponds to the linear order of keys stored in elements of the list (e.g. 1->2->3->4).
- Circular Linked Lists have the prev pointer of the head point to the tail, and the tail's next pointer point to the head.
Both images are screenshots from the incredible book "Introduction to algorithms, 3rd edition" written by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.