If you are new to data structures, this post is for you. I didn't have the easiest time grasping data structures, so I wanted to share the basics of what I have learned so far to help you get started. My previous post covered stacks and queues. This one will cover the basics of linked lists.
A linked list is an ordered collection of data made up of nodes.
- Each node must have 2 properties
- A data property which contains the data
- A next property which is a reference to the next node
class Node {
constructor(data, next=null){
this.data = data;
this.next = next
}
}
- The first node is often referred to as the "head" node and the last node is often referred to as "tail" node. The tail node will not have a reference to any other node.
- The order of nodes will not change unless we explicitly change the order by inserting and/or removing nodes.
- To access nodes, you must go through the pointers. (Linked lists do not use index numbers the same way arrays do.) Below is an example of accessing a specific node in a linked list if given an index.
getAt(index){
let count = 0
let node = this.head
while(node){
if(count === index){
return node
}
count++
node = node.next
}
return null
}
In addition to the basic singly linked list, there are 2 additional types of linked lists.
- Doubly linked list
- A doubly linked list will have both next and previous properties.
- Circular linked list
- A circular linked list doesn't have a tail node. Instead the last node will point to a node at an earlier point in the list, creating an infinite loop.
Top comments (0)