DSA Day-13

Hello!!!! I hope all of you are safe and healthy.

We’ve completed Strings and Arrays and today we’ll be starting with the next data structure on the list: Linked List

Now, one mistake that many people make while preparing for DSA is that they jump directly to linked list after arrays. You can be well versed with the concepts of linked list only after you learn about Recursion. Knowing and understanding recursion is very important while solving problems related to linked list and binary trees.

To understand recursion, you can refer to the link below. The concept is very clearly explained.

Now, before we move on to understanding linked list, let’s practice few recursion questions first:

1. https://leetcode.com/problems/n-th-tribonacci-number/
2. https://leetcode.com/problems/fibonacci-number/

Linked List Basics:

• Linked List is also a linear data structure just like arrays
• Linked lists elements are not stored at contiguous memory locations(Array elements have sequential memory access) . They can be stored anywhere in the memory but for sequential access, the nodes are linked to each other using pointers.
• Linked List is dynamic.. that is it can grow in size(unlike arrays whose size is fixed)
• Random access of elements is not allowed.. i.e. you can access elements of a linked list using index.

• Disadvantages of linked lists:

1. Random access is not allowed in Linked Lists. We have to access elements sequentially starting from the first node. So we cannot do a binary search with linked lists efficiently with its default implementation. Therefore, lookup or search operation is costly in linked lists in comparison to arrays.
2. Extra memory space for a pointer is required with each element of the list.
3. Not cache friendly. Since array elements are present at contiguous locations, there is a locality of reference which is not there in case of linked lists.

Now, many people get irritated by linked list and skip it or stop it.. but linked list is very important, because, it helps us understand the concepts of recursion, which is further used in trees. So, don’t give up. It is confusing, yes!!! But it’s important too.

PS: I used to hate linked list. I forced myself to solve the questions.. I failed many times.. it took me a lot of time, motivation and efforts to start solving. I watched a lot of videos.. went through solutions before solving questions on my own.

So, I am not saying that it is easy but you need to keep going.. because once you start solving questions on your own.. you’ll start enjoying linked list.

Now, there are few concepts of linked list that you need to understand. So, move step by step and do not skip. All you need to do today is take a notebook and pen, sit back, see the videos and try going through the concept step by step on your notebook understanding, how it is being done. No coding, just step by step following of code.

1. https://www.youtube.com/watch?v=7aEAh1cptlk : Traversing Linked List
2. https://www.youtube.com/watch?v=qKdVq81p5DU : Adding node
3. https://www.youtube.com/watch?v=yEDdNGaOkqI : Deleting a node