Interview Preparation Linked List - Revision history

Proj user4: /* Loop in the List */

2018-05-22T23:52:34Z

‎Loop in the List

Arvindallawadi: /* Removing duplicate elements */

2017-04-01T01:52:54Z

‎Removing duplicate elements

Arvindallawadi: /* Removing duplicate elements */

2017-04-01T01:50:09Z

‎Removing duplicate elements

Proj user16: /* Reverse a linked list using STL and recursion */

2016-12-20T07:20:55Z

‎Reverse a linked list using STL and recursion

Proj user16 at 07:19, 20 December 2016

2016-12-20T07:19:26Z

Proj user16 at 07:18, 20 December 2016

2016-12-20T07:18:44Z

Proj user16 at 05:46, 20 December 2016

2016-12-20T05:46:48Z

Proj user16 at 05:46, 20 December 2016

2016-12-20T05:46:18Z

Proj user16: /* Delete a node in a list */

2016-12-06T07:18:27Z

‎Delete a node in a list

Proj user16: /* Doubly Linked List */

2016-12-06T07:15:02Z

‎Doubly Linked List

@@ Line 114: / Line 114: @@
 #include <stdlib.h> /* malloc() */
-/*Function to reverse a singly linked list by iterating through the list*/
+/*Function to detect a loop in a singly linked list by iterating through the list by using two pointers
 bool ll_loop(linked_list_t* head)
+{

@@ Line 145: / Line 145: @@
-void remove_dups(linked_list_t* g_head){ //we are never deleting the head node
+void remove_dups(linked_list_t* head){ //we are never deleting the head node
-      linked_list_t* current = g_head;  //current node
+      linked_list_t* current = head;  //current node
       linked_list_t *pointer1, *duplicate;

@@ Line 145: / Line 145: @@
-void remove_dups(linked_list_t* head){
+void remove_dups(linked_list_t* g_head){ //we are never deleting the head node
-      linked_list_t* current = head;  //current node
+      linked_list_t* current = g_head;  //current node
       linked_list_t *pointer1, *duplicate;
       while(current->next != NULL){//traversing the list pointed by current
            pointer1 = current;// the current node is copied into pointer1
-           while(pointer->next != NULL){// traversing the list pointed by pointer1
+           while(pointer1->next != NULL){// traversing the list pointed by pointer1
                  if(pointer1->next->data == current->data){ //Checking for duplicates by comparing the current data and pointer1 data of next node
                     duplicate = pointer1->next;// copy the address of pointer1 node (which contains duplicate data) into duplicate
                     pointer1->next = pointer1->next->next;//placing the new address i.e. the next node address into pointer to which it will be pointing next
-                    free(pointer1);//free the pointer1 node (which contains duplicate data)
+                    free(duplicate);//free the duplicate node (which contains duplicate data)
+                    }
-                else{
+                    pointer1 = pointer1->next;//move to the next node
+                 }
             current = current->next;//current pointing to next node

@@ Line 361: / Line 361: @@
 == Reverse a linked list using STL and recursion ==
 '''''Task -''''' Reverse the values of a list of '''''n''''' integers.
 <br>
 '''''Approach:'''''

@@ Line 372: / Line 372: @@
 void listReverse(list<int>& my_list)
+{
-     if (my_list.size() <= 1) return;
+     if (my_list.size() <= 1) return; // base case
      int first = my_list.front();

← Older revision		Revision as of 07:18, 20 December 2016
Line 358:		Line 358:
	}		}
	</syntaxhighlight>		</syntaxhighlight>
		+	<BR/>
		+	== Reverse a linked list using STL and recursion ==
		+	'''''Task -''''' Reverse the values of a list of '''''n''''' integers.
		+	<br>
		+	'''''Approach:'''''
		+	<br>
		+	'''''Step 1:''''' Take out the first value of the list.
		+	<br>
		+	'''''Step 2:''''' Reverse the rest of the list recursively.
		+	<br>
		+	'''''Step 3:''''' Append the removed value to the end of the reversed rest of the list.
		+	<syntaxhighlight lang="c">
		+	void listReverse(list<int>& my_list)
		+	{
		+	if (my_list.size() <= 1) return;
		+
		+	int first = my_list.front();
		+	my_list.erase(my_list.begin()); // remove the first element
		+
		+	listReverse(my_list); // reverse the rest of the list
		+	my_list.push_back(first); // append the first element at the end
		+	}
		+	</syntaxhighlight>
		+	<BR/>

@@ Line 329: / Line 329: @@
 <br>
 This example exclusively makes use of STL Library '''''<list>''''' and '''''recursion'''''.
 '''''Approach:''''' First define function '''''member_of''''' that checks if a value '''''x'''''' is present in the list.
 <syntaxhighlight lang="c">

← Older revision		Revision as of 05:46, 20 December 2016
Line 324:		Line 324:
	</syntaxhighlight>		</syntaxhighlight>
	<BR/>		<BR/>
		+
		+	== Make List unique using STL and recursion ==
		+	The task - given a list of '''''n''''' integers in a list, remove all the duplicate values so that what remains is a list of unique values.
		+	<br>
		+	This example exclusively makes use of STL Library '''''<list>''''' and '''''recursion'''''.
		+	'''''Approach:''''' First define function '''''member_of''''' that checks if a value '''''x'''''' is present in the list.
		+	<syntaxhighlight lang="c">
		+	bool member_of(const int value, const list<int>& my_list, list<int>::const_iterator it)
		+	{
		+	if (it == my_list.end())
		+	return false;
		+	return (*it == value) \|\| member_of(value, my_list, ++it);
		+	}
		+	</syntaxhighlight>
		+	<br>
		+	Now, take out the first value. Make the rest of the list unique. Then if the value we took out is not in the rest of the list, put it back. Otherwise, leave it out.
		+	<br>
		+	<syntaxhighlight lang="c">
		+	void isListUnique(list<int>& alist)
		+	{
		+	if (alist.size() <= 1) return; // base case
		+
		+	int first = alist.front();
		+	alist.erase(alist.begin()); // remove the first element
		+
		+	isListUnique(alist); // make the rest of the list unique
		+
		+	if (!member_of(first, alist, alist.begin()))
		+	{
		+	alist.push_front(first); // put back the first element
		+	}
		+	}
		+	</syntaxhighlight>

@@ Line 273: / Line 273: @@
 <BR/>
-== Delete a node in a list==
+== Delete a node in a linked list==
 <syntaxhighlight lang="c">
 typedef struct linked_list_node {

@@ Line 219: / Line 219: @@
 <syntaxhighlight lang="c">
 typedef struct linked_list_node {
-     struct linked_list_node *next;    /*next link*/
+     struct linked_list_node *next;    /*next node*/
-     struct linked_list_node* prev;    /*previous link*/
+     struct linked_list_node* prev;    /*previous node*/
      int data;
 } linked_list_t;
@@ Line 272: / Line 272: @@
 </syntaxhighlight>
 <BR/>
 == Delete a node in a list==