LINKED LISTS VS ARRAYS, ADVANTAGES AND DISADVANTAGES

I’ve been struggling with getting a good grip on Linked Lists, so I did some research to get a firmer grasp.

I read documents, watched YouTube videos and did a couple examples.

There is a lot more to learn but here’s what I’ve learned from my research so far:

LINKED LISTS

1. A sequence of elements, where each element links to the next element, which links to the next element.

2. A linked list can contain pretty much any data, strings, characters, numbers.

3. The elements can be unsorted or sorted.

4. Can contain unique elements or duplicate elements.

5. Array elements are indexed, but with linked lists, you have to start at the HEAD and work your way through until you get to the element you want.

6. The beginning of the linked list is stored in a “head” pointer which points to the first node.

7. The last node of a linked list usually is called the tail of the list

8. Thus, we can traverse the list starting at the head and ending at the tail.

9. The tail node is a special node, where the next pointer is always pointing or linking to a null reference, indicating the end of the list.

10. The next reference inside a node can be viewed as a link or pointer to another node.

Here are some ADVANTAGES and some DISADVANTAGES of using Linked Lists:

ADVANTAGES

1. Insertion and deletion can be very quick.

2. If you want to insert an element to the beginning of the list, this can be done in constant time.

a. O(1) if you want to prepend.

3. If you want to delete an element from the beginning of the linked list, this can be done in constant time.

4. If you want to append an element to the end of a linked list, that might require walking all the way through the linked list until you get to the very last element and then insert the element there. That will take linear time.

a. O(n) if you want to append.

5. Because elements can be stored anywhere in memory, adding and removing elements is much faster than an array.

DISADVANTAGES

1. slow to get to nth element

2. O(n) that is linear!

Here are some similarities and some differences between Arrays and Linked Lists.

Arrays and Linked Lists share many properties.

ARRAYS

1. FIXED SIZE

a. Arrays can only be a fixed size.

2. INEFFICIENT INSERTION AND DELETION

a. Insertion time for arrays is Big O of n (O(n)) as n elements must be shifted. However, inserting and deleting form the end of an array is O(1).

3. RANDOM ACCESS i.e., EFFICIENT INDEXING

a. If you want the element at index 7, you can immediately retrieve the element at index 7.

b. arr[7]

c. arrays support direct access

4. MAY RESULT IN MUCH MEMORY WASTE

a. To make up for the fact that arrays can only be made at a fixed size, sometimes they can be created a lot bigger than what you really need to make you have enough room for everything

5. SEQUENTIAL ACCESS IS FASTER

a. REASON: ELEMENTS IN CONTIGUOUS MEMORY LOCATIONS.

LINKED LIST

1. DYNAMIC SIZE

a. You can keep adding links and you don’t have to do anything differently.

2. EFFICIENT INSERTIONS AND DELETIONS

a. Inserting a new node to the beginning or end of a linked list takes constant time (O(1)) as the only steps are to initialize a new node and then update the pointers.

b. Deleting nodes at the beginning and end of the linked list take constant time (O(1)).

c. Insertion to the middle of the linked list takes linear time (O(n)) as iteration over n elements is required to get to the correct location before inserting the node.

d. Deleting a node in the middle of the linked list takes linear time (O(n)).

3. NO RANDOM ACCESS

a. If you want the element at index 7, you can have to start at the HEAD and make your way through the linked list to the element at index 7.

b. That takes linear time, which is quite a bit slower.

c. Linked Lists support sequential access.

4. NO WASTE OF MEMORY

a. Because of the dynamic size, there is no wasted memory.

b. The size for a linked list is not pre-defined, allowing the linked list to increase or decrease in size as the program runs.

5. SEQUENTIAL ACCESS IS SLOW

a. REASON: ELEMENTS NOT IN CONTIGUOUS MEMORY LOCATIONS.

There is a lot more to learn and I will continue to learn more about Linked List and the other Data Structures as well.

Here are some of the YouTube videos and documents I read that helped get a better understanding of Linked Lists

Data Structures: Linked Lists from HackerRank and Linked List — Beau teaches JavaScript from freeCodeCamp.org did a great job of explaining the Advantages and Disadvantages of Linked Lists, they also had good examples, and you could code-along and try it for yourself.

Linked Lists | Data Structures in JavaScript from beiatrix explained memory allocation in a way that I could understand, it was so good.

I’m definitely going to watch beiatrix’s other videos on her playlist on Data Structures in JavaScript.

Of all the research I’ve done, Linked List Data Structure | JavaScript from Traversy Media had the best code along that I understand and follow along.

Linked Lists vs. Arrays by Hermann Krohn helped a whole lot in understanding the differences and similarities between Linked Lists and Arrays.

Linked List Basics By Nick Parlante

CS240 — Lecture Notes: Singly Linked List by Daisy Tang