cpppro

Archive for April, 2007|Monthly archive page

Sorting a Linked List with Selection Sort

In C Tidbits, Data Structures in C/C++ on April 29, 2007 at 7:26 pm

The basic idea of selection sorting algorithm is

1)find minimum element in the list
2)swap it with the beginning element
3)repeat the above steps after moving pointer to next element

Here is the graphical representation of operation of this algorithm…

selection sort array pic

Before we go to linked list sorting understand how do we sort for an array…
Here is the C code for selection sort for an array

 

Please refer http://www.refcode.net/2013/02/sorting-linked-list-with-selection-sort.html

 

Detecting a loop in single linked list

In C Tidbits, Data Structures in C/C++ on April 22, 2007 at 7:07 pm

Please refer this post for linked list basics and all other operations on linked lists.

 

Loops in linked list can be detected by inserting dummy nodes after every node, so if we find dummy node after a node already, that says that list has a loop. The diagram below explains this. This method takes O(n) time and O(n) additional space.
detecting loops

Loops in linked list can also be detected by running two loops paralally, one loop traverse list by one node, another loop traverse list by skipping a node while going to next node. this way they meet at some point of time, if the list has a loop. The diagram below explains this. This method takes O(n) time in best case.
detecting loops another method

program for finding loop by traversing with two pointers… this program takes input as linked list, returns a node(where a loop starts), or returns NULL if we could not find a loop…

Node *detectloop(Node *list)
{
  Node *n1, *n2;

  //prev indicates loop started at this point
  Node *prev=NULL;

  for(n1=list, n2=list; (n1!=NULL) && (n2!=NULL); )
  {
    if (prev && (n1 == n2))
    {
      return prev;
    }
    prev = n1;
    n1=n1->next;
    n2=n2->next;
    if (n2)
    {
      n2=n2->next;
    }
  }
}

comments?

C/C++ Interview algorithms

In Algorithms, Data Structures in C/C++, Question Patterns on April 17, 2007 at 10:35 pm

1. Reverse a singly linked list

//
// iterative version
//
Node* ReverseList( Node ** List )
{
  Node *temp1 = *List;
  Node * temp2 = NULL;
  Node * temp3 = NULL;

  while ( temp1 )
  {
    //set the head to last node
    *List = temp1;

    // save the next ptr in temp2
    temp2= temp1->pNext;

    // change next to privous
    temp1->pNext = temp3;
    temp3 = temp1;
    temp1 = temp2;
  }

  return *List;
}

2. Delete a node in double linked list

void deleteNode(node *n)
{
  node *np = n->prev;
  node *nn = n->next;
  np->next = n->next;
  nn->prev = n->prev;
  delete n;
}

3. Sort a linked list

//sorting in descending order
struct node
{
  int value;
  node* NEXT;
}
//Assume HEAD pointer denotes the first
//element in the linked list
//only change the values? don't have to
//change the pointers
Sort( Node *Head)
{
  node* first,second,temp;
  first= Head;
  while(first!=null)
  {
    second=first->NEXT;
    while(second!=null)
    {
      if(first->value value)
      {
        temp = new node();
        temp->value=first->value;
        first->value=second->value;
        second->value=temp->value;
        delete temp;
      }
      second=second->NEXT;
    }
    first=first->NEXT;
  }
}

4. Reverse a string

void ReverseString (char *String)
{
  char *Begin = String;
  char *End = String + strlen(String) - 1;
  char TempChar;

  while (Begin < End)
  {
    TempChar = *Begin;
    *Begin = *End;
    *End = TempChar;
    Begin++;
    End- -;
  }
}

5. Insert a node a sorted linked list

void sortedInsert(Node * head, Node* newNode)
{
  Node *current = head;

  // traverse the list until you find
  //item bigger the new node value
  //
  while ((current!= NULL) &&
         (current->data data))
  {
    current = current->next;
  }
  //
  // insert the new node before the big item
  //
  newNode->next = current->next;
  current = newNode;
}

6. Covert a string to upper case

void ToUpper(char * S)
{
  while (*S!=0)
  {
    *S=(*S >= 'a' && *S <= 'z')?(*S-'a'+'A'):*S;
    S++;
  }
}

7. Multiple a number by 7 without using * and + operator.

Linked Lists

In C Tidbits, Data Structures in C/C++, Pointers & Callbacks, Tutorials on April 12, 2007 at 2:55 pm

Linked Lists Basics
[Download this tutorial as linked lists tutorial , for updated conetnt and comments, generate a new pdf with the option which is present below the post]

What are Linked Lists?
Linked lists store collections of data like arrays.  Linked lists are chain of records/nodes, one record/node points to the next. Record holds the data.

Why Linked Lists?
There are several  disadvantages with arrays, here are some…
1) The size of the array is fixed. Most often this size is specified at compile time however the size of the array can be deferred until the array is created at runtime (from heap), but after that it remains fixed. This causes to waste memory eventhough e may not use.
2) Inserting new elements at the front is potentially expensive because existing elements need to be shifted over to make room.
3)When array was full, to insert more data, it need to be resized, this operation is quite expensive, even may not be possible if in case memory got fragmented.
Linked lists performs well where arrays fail to do it.
Please refer http://www.refcode.net/2013/02/linked-lists.html

 

Sorting A Linked List with Bubble Sort

In C Tidbits, Data Structures in C/C++, Pointers & Callbacks on April 11, 2007 at 10:01 pm

The basic idea of this sorting algorithm is to
compare two neighboring objects, and to swap them if
they are in the wrong order.

here is an example, which shows sorted list in several passes..

5   10   20   13   7   17
5   10   13   7    17  20
5   10   7    13   17  20
5   7    10   13   17  20
5   7    10   13   17  20

Here’s a snippet of C code for bubble sort for sorting an array:

Please refer http://www.refcode.net/2013/02/sorting-linked-list-with-bubble-sort.html