Data Structures and Algorithms

(Yeah, it's probably going to be long README, I'll make it neat after I cover most of the DS Concepts, consider this repo as a DSAhub)

1. Linked List

It's a DS used for storing collections of data.

1.1 Props:

Elements are connected by pointers.
It can grow or shrink in size during runtime.
Memory allocation is done as list grows.

Figure: Image of a linked List

1.2 Advantages of using Linked Lists

It can be expanded in constant time.
Unlike arrays, there is no wastage of memory upfront.

1.3 Disadvantages of using Linked Lists

Has O(n) access time unlike the array which has O(1).
Memory wastage in terms of extra reference pointers.
In some cases, it is hard to manipulate.

1.4 Parameters

- Indexing: 						O(n)
- Insertion/Deletion at beginning: 	O(1)
- Insertion at the end: 			O(n)
- Deletion at the end: 				O(n)
- Insertion/Deletion in middle: 	O(n)
- Wasted space: 					O(n) (for pointers)

1.5 Singly Linked Lists

Each node contains a pointer which is pointed towards the next node. Last node is pointed to NULL (to indicate the end of the list).

Below, you can find a general type declaration of a singly linked list:

struct Node{
	int data;
	struct Node *next;
};

1.5.1 Basic Operations

a) Traversing lists b) Inserting an item c) Deleting an item

Traversing How would you traverse? Simple, follow the pointers, display/count the nodes if you like and stop when the pointer points to NULL.

PseudoCode for Traversal

int traversal(struct Node *head){
	struct Node *current=head;
	int count=0;
	while (current!=NULL){
		count++;
		printf("%i",&current->data);
		}
	return count;
	}

Time Complexity: O(n) Space Complexity: O(1)

Inserting a node in Linked List

It can be done in 3 ways:

Inserting before head
Inserting after tail
Inserting at any random location in between head and tail

Inserting before head'

Logic: new node's next pointer points to head and the head pointer now must point to the new node.

Update next pointer of new node, to point to the current head.
Update the head pointer to the new node.

Inserting After Tail

Logic: Last Node's next pointer should point towards new Node. New node should point towards NULL.

Inserting at any random location between head and tail node

Note: In this case, 2 pointers need to be maintained. Pointers pointing to current node and the node previous to the current node. One point to observe here is that if you want to insert your node at position 'x', you should first traverse till position 'x-1'. We'll call this x-1th node the position node.

Logic: new node's next pointer should point towards position node's next pointer.

position node's next pointer will now point towards new node.

void insertLinkedList (struct Node **head, int data, int postition)
{
	int k=1;
	struct Node *p, *q, *newNode;
	newNode = (Node *)malloc(sizeof(struct Node));
	if (!newNode){
		printf("Memory Error"); //why is it so?
		return;
	}
	newNode->data=data;
	p =*head;
	// inserting at the beginning
if (position==1){
newNode->next=p;
*head=newNode;
}
else{
	//Traverse the list until the position where we want to insert
	while ((p!==NULL) && (k<position)){
	k++;
	q=p;
	p=p->next;
	}
	p->next=newNode;
	newNode->next=p;
}
}

joel-razor1/DSAlgo