Linked List

Implemented using pointers,

typedef struct node{
    int value;
    struct node* next;
}listnode;

listnode*head = NULL;
listnode*tail = NULL;

Primary operations :

1) searching
2) insertion
3) deletion

Searching can be done in two ways , either iteratively or recursively recursive code : simple
if-else recursive method. type : tail recursive. base case -> either list is empty or value found at head

listnode* search(listnode*head,int x)
{
    if(head==NULL)
        return;
    else if(head->value==x)
        return head;
    else
    return search(head->next,x);
}

time complexity : O(n) space complexity: O(1)

Insertion in a list :


important cases :
1) list can be empty, so head pointer will have to be adjusted,
2) pass address of the head and tail pointer in addnode() function.
3) otherwise simply insert at the tail of the list and update the tail pointer.

void addnode(listnode**head,listnode**tail,int value)
{
	listnode* temp = (listnode*)malloc(sizeof(listnode));
	temp->value = value;
	temp->next = NULL;
	
	if(*head == NULL) //list was empty
	{
		*head = temp;
		*tail = *head;   // adjust tail pointer
	}
	
	else
	(*tail)->next = temp;   // add at the end of tail
	*tail = (*tail)->next;  // adjust tail pointer
	return ;
}

Deletion : find the pointer to the node that is to be deleted and remove the desired node from the list. 

Why linked list is preferred ?:
1) insertions and deletions are simple as compared to arrays where number of elements have to be shifted
2) linked list are recursive objects : cut the first element , and what we have is another linked list. 

Important operations and questions about linked lists

1) reverse a linked list
 a) recursive
b) iterative

2) sort a linked list
a) using bubble sort technique
b) using merge sort {best way under normal condition}

3) doubly linked list {repeat 1, and 2 for the doubly linked list }

4)detect whether a linked list contain a loop or not, find and remove the loop

5) find the middle of the linked list 6) find the nth node from the last in a linked list

7) reverse alternate k nodes in a singly linked list 

8) remove duplicates from sorted/unsorted singly linked list

9) print a linked list in reverse order

10) given two linked list , find their point of intersection

11) generate doubly linked list from a binary search tree

12) insert nodes into the list in sorted fashion

13) given a linked list of characters, check whether it is palindrome or not

// todo :