Insertion - All kinds
ListNode *insertBeforeHead(ListNode *head, int X)
{
if (!head)
return new ListNode(X);
ListNode *node = new ListNode(X);
node->next = head;
head->prev = node;
return node;
}
ListNode *insertBeforeTail(ListNode *head, int X)
{
ListNode *node = new ListNode(X);
if (!head)
return node;
if (!head->next)
{
node->next = head;
head->prev = node;
return node;
}
ListNode *temp = head;
while (temp->next)
temp = temp->next;
ListNode *behind = temp->prev;
behind->next = node;
node->next = temp;
node->prev = behind;
temp->prev = node;
return head;
}
ListNode *insertBeforeKthPosition(ListNode *head, int X, int K)
{
ListNode *node = new ListNode(X);
if (!head)
return node;
if (!head->next || K == 1)
return insertBeforeHead(head, X);
ListNode *temp = head;
int cnt = 0;
while (temp)
{
cnt++;
if (cnt == K)
break;
temp = temp->next;
}
ListNode *behind = temp->prev;
ListNode *ahead = temp->next;
if (!ahead)
return insertBeforeTail(head, X);
behind->next = node;
node->prev = behind;
node->next = temp;
temp->prev = node;
return head;
}
void insertBeforeGivenNode(ListNode *node, int X)
{
ListNode *newNode = new ListNode(X);
ListNode *behind = node->prev;
behind->next = newNode;
newNode->next = node;
node->prev = newNode;
newNode->prev = behind;
}
Deletion - All Kinds
ListNode *deleteHead(ListNode *head)
{
if (!head || !head->next)
return NULL;
ListNode *lead = head;
head = head->next;
head->prev = NULL;
delete lead;
return head;
}
ListNode* deleteTail(ListNode* head) {
if(!head || !head->next) return NULL;
ListNode* tail = head;
while(tail->next) tail=tail->next;
ListNode* behind = tail->prev;
behind->next = NULL;
tail->prev = NULL;
delete tail;
return head;
}
ListNode* deleteKthElement(ListNode* head, int k) {
ListNode* temp = head;
int cnt=0;
while(temp){
cnt++;
if(cnt==k) break;
temp=temp->next;
}
ListNode* behind = temp->prev;
ListNode* ahead = temp->next;
if(!behind && !ahead){
delete head;
return NULL;
}else if(!behind) return deleteHead(head);
else if(!ahead) return deleteTail(head);
else{
behind->next = temp->next;
ahead->prev = temp->prev;
temp->next = temp->prev = NULL;
delete temp;
return head;
}
return head;
}
void deleteGivenNode(ListNode* node) {
ListNode* behind = node->prev;
ListNode* ahead = node->next;
if(!ahead){
behind->next=NULL;
node->prev=NULL;
delete node;
return;
}
behind->next=node->next;
ahead->prev=node->prev;
node->next=node->prev=NULL;
delete node;
}