LinkedList | Python | Basics to Advance
Tags: programming, tutorial
Published: 2022-06-27 11:33:23

## 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` and `next`
- This `data` can be anything, from just an `int` to an array or dictionary.
- `next` is a pointer which points towards the next `Node`
- `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.


![Linked_Link_In_Action](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v2gyexd0xic6tfv9rzzi.gif)

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:
```python
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.

```python
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:

```python
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](https://www.pexels.com/photo/selective-focus-photoraphy-of-chains-during-golden-hour-119562/)