How memory works
Imagine your three friends and you are going to the cinema.
Each seat accommodate one person. There are four of you guys - so you will need four seats.
And you’re ready for the movie! This is basically how your computer’s memory works. Your computer are like seats at the cinema, and each seat has an address.
dabeeb2 is the address of a slot in memory.
Each time you want to store an item in memory, you ask the computer for some space, and it gives you an address where you can store your item. If you want to store multiple items, there are two basic ways to do so: arrays and lists. I’ll talk about arrays and lists next, as well as the pros and cons of each. There isn’t one right way to store items for every use case, so it’s important to know the differences.
Arrays and Linked Lists
Sometimes you need to store a list of elements in memory. Suppose you’re writing an app to manage your todos. You’ll want to store the todos as a list in memory.
Should you use an array or a linked list? Let’s store the todos in an array first, because it’s easier to grasp. Using an array means all your tasks are stored contiguously (right next to each other) in memory.
Now suppose you want to add a fourth task. But the next seat is taken up by someone else!
It’s like going to a movie with your friends and finding a place to sit— but another friend joins you, and there’s no place for them. You have to move to a new spot where you all fit. In this case, you need to ask your computer for a different chunk of memory that can fit four tasks. Then you need to move all your tasks there.
If another friend comes by, you’re out of room again—and you all have to move a second time! What a pain. Similarly, adding new items to
an array can be a big pain. If you’re out of space and need to move to a new spot in memory every time, adding a new item will be really slow. One easy fix is to “hold seats”: even if you have only 3 items in your task list, you can ask the computer for 10 slots, just in case. Then you can add 10 items to your task list without having to move. This is a good workaround, but you should be aware of a couple of downsides:
• You may not need the extra slots that you asked for, and then that memory will be wasted. You aren’t using it, but no one else can use it either.
• You may add more than 10 items to your task list and have to move anyway.
So it’s a good workaround, but it’s not a perfect solution. Linked lists solve this problem of adding items.
Linked lists
With linked lists, your items can be anywhere in memory.
Each item stores the address of the next item in the list. A bunch of random memory addresses are linked together.
It’s like a treasure hunt. You go to the first address, and it says, “The next item can be found at address 123.” So you go to address 123, and it says, “The next item can be found at address 847,” and so on. Adding an item to a linked list is easy: you stick it anywhere in memory and store the address with the previous item.
With linked lists, you never have to move your items. You also avoid another problem. Let’s say you go to a popular movie with five of your friends. The six of you are trying to find a place to sit, but the theater is packed. There aren’t six seats together. Well, sometimes this happens with arrays. Let’s say you’re trying to find 10,000 slots for an array. Your memory has 10,000 slots, but it doesn’t have 10,000 slots together. You can’t get space for your array! A linked list is like saying, “Let’s split up and watch the movie.” If there’s space in memory, you have space for your linked list.
If linked lists are so much better at inserts, what are arrays good for?
Arrays
Websites with top-10 lists use a scummy tactic to get more page views. Instead of showing you the list on one page, they put one item on each page and make you click Next to get to the next item in the list. For example, Top 10 Best TV Villains won’t show you the entire list on one page. Instead, you start at #10 (Newman), and you have to click Next on each page to reach #1 (Gustavo Fring). This technique gives the websites 10 whole pages on which to show you ads, but it’s boring to click Next 9 times to get to #1. It would be much better if the whole list was on one page and you could click each person’s name for more info.
Linked lists have a similar problem. Suppose you want to read the last item in a linked list. You can’t just read it, because you don’t know what address it’s at. Instead, you have to go to item #1 to get the address for item #2. Then you have to go to item #2 to get the address for item #3. And so on, until you get to the last item. Linked lists are great if you’re going to read all the items one at a time: you can read one item, follow the address to the next item, and so on. But if you’re going to keep jumping around, linked lists are terrible.
Arrays are different. You know the address for every item in your array. For example, suppose your array contains five items, and you know it starts at address 00. What is the address of item #5?
Simple math tells you: it’s 04. Arrays are great if you want to read random elements, because you can look up any element in your array instantly. With a linked list, the elements aren’t next to each other,
so you can’t instantly calculate the position of the fifth element in memory—you have to go to the first element to get the address to the second element, then go to the second element to get the address of the third element, and so on until you get to the fifth element.
What we have been discussed so far is a Singly Linked List (a list consisting of items in which each item knows the location of the next item) while a A Doubly Linked List is a list that has two references, one to the next node and another to previous node.
Singly Linked List Implementation in Ruby
list = {
head: {
value: 12
next: {
value: 99
next: {
value: 37
next: null
}
}
}
}
Access value using dot notation:
list.head.next.next.value; // -> 37
In order to create a linkedList from scratch you need two classes: A node class and a Linkedlist class.
class Node
attr_accessor :value, :next
def initialize(value, next_node)
@value = value
@next = next_node
end
end
This class creates a node object with a value and a next which will point to the next node (originally it starts as nil, and when a new node is created nill will be replaced with that value)
class LinkedList
def initialize(value)
@head = Node.new(value, nil)
end
def add_to_list(value)
current_node = @head
while current_node.next != nil
current_node = current_node.next
end
current_node.next = Node.new(value, nil)
end
def delete(value)
current_node.next = @head
if current_node.value = value
@head = current_node.next
else
while (current_node.next != nil) && (current_node.next.val != val)
current_node = current_node.next
end
unless current_node.next == nil
current_node.next = current_node.next.next
end
end
end
def return_list
elements = []
current_node = @head
while current_node.next != nil
elements << current_node
current_node = current_node.next
end
elements << current
end
end
1) Initialize → this method creates a list by creating a head node with a value and a next pointer being nil
2) Add → this method starts by finding the last node, by looping through the nodes until the next one is nil, then it makes nil be replaced by a new node object
3) Delete → This method starts by saying if the value to delete is the head, just make @head equal to the next node, otherwise loop through the nodes until the next node is the value to delete. Once that one is found replace the next node with the next next node
4) Return_list → this method pushes each node into an array so that you can show the list in array form
Uses Cases
So when is preferable to use a Linked List?
We need to do a lot of insertions and removals on a list of arbitrary (unknown at compile-time) length since insertions and deletions are simpler than for array.
Searching is not that important.
For large data, moving pointers is easier and faster than moving items themselves (not so relevant in JS).
Overflow on list will never occur because it doesn’t require a contiguous block of memory, unless the memory is actually full (not so relevant in JS).
We need to split or combine different list together, because splitting and joining lists is very efficient.
Arrays are preferable whe
Linked List required extra space for storing pointers.
Can’t really randomly access an item in the list — there is no real index to access item like in array.
Arrays allow better memory locality and cache performance.
Stay tune to learn about Big O Notation next time!
Top comments (0)