Why we should learn this?
We all know data structures and algorithms are the foundation of being a good software engineer.
Usually these foundation concepts are considered to be worthy only if you are in university or you are preparing for an interview for a big tech company.
But I have a different take on this. As an engineer you should be asking yourself this question: "As an engineer should I know X?" and if the answer is yes then please put some time in that topic to be a good engineer in general not because you are trying to score a job.
So, the questions is, as engineers - you think we should know the most basic but useful data structure called Linked-List?
I heard a big yes!!
So let's begin:
Definition and Dictionary
- Linked list is a linear data structure.
- Basically it contains only two things:
data
andnext
- This
data
can be anything, from just anint
to an array or dictionary. -
next
is a pointer which points towards the nextNode
-
Node
is just a name we use for every linked entity in the linked list. Node is somewhat similar to what you have in array as an index.
So in simple words, linked list is collection of Nodes
linked together with pointers.
Why this data structure even exists?
One may ask, we already have a linear data structure known as arrays
then why we created a similar but new one? Why?
Then let me ask a question:
How do you add a new element in the middle of an array?
- Find where you want to add new element.
- Add new element
- And shift the rest of the array one
Linked lists solve such issues like shifting the array after adding a new element in the middle.
Implementation
In python, it is really easy create some classes to reflect this data structure, like the code given below:
class LinkedList:
def __init__(self, head=None):
self.head = None
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
Creating from Array
You might be wondering how can you create this linked list and see it in action.
For this we can write a simple function to create a linked list from array and then visit every node of the linked list with another function.
def createFromArray(nodeList):
ll = LinkedList()
prev = None
for n in nums:
curr = Node(n)
if not prev:
ll.head = curr
else:
prev.next = curr
prev = curr
return ll
# Make linked-list from array - O(n)
nums = [1,2,3,4,5]
ll = createFromArray(nums)
Traversing
For traversing or in simple words - visiting all nodes in a linked list we can do something like this:
def traverseList(ll):
curr = ll.head
while curr:
print(curr.data, end=" -> ")
curr = curr.next
# traverse a linked-list O(n)
traverseList(ll)
If you like this and want to learn more, just stick along and next we will talk about some common operations on linked list.
Happy coding.
Credits:
- Cover Photo by Joey Kyber
Top comments (0)