CONCEPT OF LINKED LIST IN C

Data Structure: Linked Lists

A Linked List is a set of dynamically allocated nodes, arranged in such a way that each node contains one value and one pointer. The pointer always points to the next member of the list. If the pointer is NULL, then it is the last node in the list.

A linked list is held using a local pointer variable which points to the first item of the list. If that pointer is also NULL, then the list is considered to be empty.

Advantages of Linked Lists over Arrays:

• Arrays are bound by the limitation of their size. You have to specify the number of elements in the array beforehand. Whereas in the linked list you can add any number of elements.
• Suppose you have to insert any element at the beginning in an array then you will have to shift all the elements one place right to make room for the new element. This operation is expensive as it takes O(n) time. Whereas you can insert any element at the beginning in the linked list in O(1) time. Same is the case with deletion of elements.

Disdvantages of Linked Lists over Arrays:

• If the array is sorted you can apply binary search to search any element. But even if linked list is sorted you cannot apply binary search and so the complexity of searching in linked list is O(n).
• Extra memory space is required for the pointer with each element in the linked list.
• Arrays have better cache locality than linked list which can greatly affect it's performance.

Difference between Arrays and Linked Lists:

To clear your concepts you can follow these steps...

Step 1: Visit this article to clear your basic theory

Step 2: Visit this article to deep-dive into Queue

Some additional see-through contents...

1. Introduction to Linked List

2. Types of Linked List

3. Arrays vs. Linked List

4. Insertion in Linked List

5. Deletion in Linked List

Problem Set: Level Basic

1.  Write a program to create and traverse in a linked list.(Solution)

2. Write a program to search a node in a linked list.(Solution)

3. Write a program to insert a node at end.(Solution)

4. Write a program to insert a node at beginning.(Solution)

5. Write a program to insert a node at middle.(Solution)

6. Write a program to delete the ending node.(Solution)

7. Write a program to delete the starting node.(Solution)

8. Write a program to delete a node from middle.(Solution)

Problem Set: Level Intermediate

1. Rearrange a linked list such that all even and odd positioned nodes are together

Rearrange a linked list in such a way that all odd position nodes are together and all even positions node are together, (Solution)

Examples:

Input:   1->2->3->4
Output:  1->3->2->4

2. Decimal Equivalent of Binary Linked List

Given a singly linked list of 0s and 1s find its decimal equivalent. (Solution) 

Examples:                  

   Input  : 0->0->0->1->1->0->0->1->0
   Output : 50   

3. Check if a linked list is Circular Linked List (Solution)

4. Flattening a Linked List

Given a linked list where every node represents a linked list and contains two pointers of its type:
(i) Pointer to next node in the main list (we call it ‘right’ pointer in below code)
(ii) Pointer to a linked list where this node is head (we call it ‘down’ pointer in below code).
All linked lists are sorted. See the following example

       5 -> 10 -> 19 -> 28
       |    |     |     |
       V    V     V     V
       7    20    22    35
       |          |     |
       V          V     V
       8          50    40
       |                |
       V                V
       30               45

5. Detect loop in a linked list  (Solution)    

6. Find Length of a Linked List (Iterative and Recursive) (Solution)

7. Write a function to get Nth node in a Linked List

Write a GetNth() function that takes a linked list and an integer index and returns the data value stored in the node at that index position. (Solution)

Example:

Input:  1->10->30->14,  index = 2
Output: 30  
The node at index 2 is 30

8. Print reverse of a Linked List without actually reversing (Solution)         

9. Search an element in a Linked List (Iterative and Recursive) (Solution)

10. Detect and Remove Loop in a Linked List (Solution)

11. Convert a given Binary Tree to Doubly Linked List

Given a Binary Tree (BT), convert it to a Doubly Linked List(DLL). The left and right pointers in nodes are to be used as previous and next pointers respectively in converted DLL. The order of nodes in DLL must be same as Inorder of the given Binary Tree. The first node of Inorder traversal (left most node in BT) must be head node of the DLL.  (Solution)

12. Remove duplicates from a sorted linked list

Write a function which takes a list sorted in non-decreasing order and deletes any duplicate nodes from the list. The list should only be traversed once.

For example if the linked list is 11->11->11->21->43->43->60 then removeDuplicates() should convert the list to 11->21->43->60. (Solution)