What is a linked list?
A linked list is a data structure that consists of a sequence of nodes, where each node contains some data and a pointer (or reference) to the next node in the sequence.
Unlike arrays, which have a fixed size (depending on the language), and store elements in contiguous memory locations, linked lists can dynamically allocate memory for nodes as they are added, and do not need to store elements in contiguous memory locations. This makes linked lists more flexible than arrays, but also potentially less efficient for certain operations, such as random access to elements.
A singly linked list has each node pointing only to the next node in the sequence, with the last node pointing to null to indicate the end of the list. This means that you can only traverse the list in one direction, from the head (the first node) to the tail (the last node).
聽
Linked lists can be used for a variety of purposes, such as implementing stacks, queues, and hash tables. However, they can be less efficient than arrays for certain operations, such as searching for an element in the middle of the list, since you must traverse the list from the beginning to find it.
How linked lists look in practice?
First, we need to define our node class. As mentioned before, each node should have a reference to the next node.
class Node<T> { public data: T; public next: Node<T> | null; constructor(data: T) { this.data = data; this.next = null; } }
聽
Now, we can create our Linked List class.
聽
class LinkedList<T> { protected head: Node<T> | undefined }
This is the basic structure of our class. Now let's create a basic method to make this class a little more complete.
Let's start with the push method.
class LinkedList<T> { protected head: Node<T> | undefined push(element: T): void { const node = new Node(element) let current; if(this.head == null) { this.head = node } else { current = this.head while(current.next != null) { current = current.next } current.next = node } } }
聽
First of all, we need to create a new node with the value passed as the method's parameter. Now, we need to check if there is a head of our LinkedList class. If not, our new Node becomes the Header of our class. But if there is, we need to walk through the Linked list until we find the tail (the Node that the next property points to as null).
That was a brief demonstration about LinkedLists. I have a more complete example on my GitHub. Would you like to take a look? 馃榾
聽