Single Linked List
Last updated
Was this helpful?
Last updated
Was this helpful?
A linked list consists of nodes where each node contains a data field and a reference(link) to the next node in the list. - geeksforgeeks.org
Push: Insert an element at the end of the linked list.
Insert: Insert an element at the given index of the linked list.
Remove: Remove the end element of the linked list.
RemoveAt: Remove the element at the given index of the linked list.
GetElementAt: Get the element at the given index of the linked list.
IndexOf: Return the index of the element in the linked list.
Let us define the ES6 class Node, with two properties data and next, data property will hold, the data which we will insert in the linked list and next property will hold, the pointer to the next Node. A Linked List is just a chain of Node linked to each other by next pointer. What's a pointer? A pointer points to the next member of the list, as you see in the above image.
Now, Let's define the ES6 class linked list with three properties, count to track the number elements in the linked list. the head which will always point to the starting node of the linked list but initially it will be undefined and equalFun to compare two nodes in the linked list . In a single Linked list, we only have a reference to the head node. So to traverse the linked list we always start with the head and walk through it. So, subsequent method we will always start with head.
When adding an element at the end of the linked list, there can be two scenarios:
When the head is undefined i.e linked list is empty.
When the linked list is not empty we need to append at the end.
First, we create a Node passing element as its value if the head is undefined then assign head to the node ({1}) else ,we will define a current variable equal to head and loop until we reach the end of the linked list i.e when node's next is null ({2}) and assign the end Node's next to the node ({3}), after adding an element will always increment the count variable ({4}).
To get an element by its index we will first define a variable node, referring to head ({1}), we valid the index's out of bound error, by check is the index, greater than zero and less than count. ({2}); if not then return undefined ({5}), Now, iterate over the linked list starting from 0 to the index and ({3}), return the node ({4}). This method will be very useful in insert and remove an element from any position in the linked list.
Insert an element at a given the position; the index must be greater than zero and less than and equal to count, there are two scenarios, we will first define a variable node which refers to the head.
index is equal to zero ({1})
check if the head is undefined or not
if undefined than head equal to the node
else change the head node to the new node and node's next to the previous head.
index is greater than zero ({2})
adding an element in the middle or at the end of the list. First, need to loop through the list until we reach the desired position. In this case, we will loop to index -1, meaning one position before where we desire to insert a new node
When we get out of the loop, the previous variable will be reference to an element before the index where we would like to insert to new element, and the current variable .
So , first we link the node's next to current and then change the link between previous and current. we need previous.next to the node.
This method will return the index of the given element if exists else return -1 ({4}) . To find the index of the element, we will start with the head element ({1}) and loop until the element is found ({2}) and returns its index ({3}) .
Remove an element at the specified index, we first check if the linked list is empty else return undefined ({1}) ,After that we valid the index's out of bound error, by check is the index, greater than zero and less than count.
We want to remove the first element i.e index equal to zero ({2}), shift the head to the next node. We will refer to the first element of the list using the current variable. If we assign head to current's next, we will remove the first element ({3}).
We want to remove the last element or an element from the linked list, we will use getElementAt method to get the one previous element using index -1 ({4}), current will be previous's next ({5}). So, to remove the current node, all we have do is to link the previous.next to current.next ({6}).
To remove an element, we check if the linked list is not empty. If not then get the index of the element using the indexOf method if the index is -1 then the element doesn't exist else use the index and remove the element from the linked list using removeAt method.
you get the full source here
Methods
Complexity
insert at any position
O(n)
insert at head
O(1)
GetElementAt
O(n)
indexOf
O(n)
remove head element
O(1)
remove any element(removeAt)
O(n)