refer double linked list post for information about double linked list. Here in this post we will be discussing about reversing a double linked list.

Here is the pictorial representation of our algo…

in our routine we will swap our next, prev pointers of nodes to reverse the double linked list… this routine capable of reversing entire list for given any node in the double linked list.

The below routine takes input as any node in double linked list and reverse the entire double linked list and returns same node pointer.

Node *reverselist(Node *head)
{
  Node* n = head;
  Node *tmp, *tmp2;
  Node* after = head->next;
  Node* before = head->prev;
 
  //reverse all nodes after n (if any)
 
  //now reverse nodes after head
  while(n && after)
  {
    tmp = after->next;
    tmp2 = after;
 
    after->next = n;
    n->prev = after;
 
    after = tmp;
    n = tmp2;
  }
  //make the last node prev ptr points to NULL
  n->prev = NULL;
 
  //search all nodes before n (if any)
  n = head;
 
  //now reverse all nodes before head
  while(before && n)
  {
    tmp = before->prev;
    tmp2 = before;
 
    before->prev = n;
    n->next = before;
 
    before = tmp;
    n = tmp2;
  }
  //make the first node next ptr points to NULL
  n->next = NULL;
 
  return head;
}

any comments welcome…

Popularity: 51%

Here is a routine which does find out broken links in double linked list, wondering what is a broken link…

here is the code snippet for detecting broken links in double linked list…

for complete operations (all operations) on double linked list, visit earlier post

int detectbrokenlist(Node *n)
{
  int brokenlinks = 0;
  Node *tmp = n;
  Node* after = n->next;
  Node* before = n->prev;
 
  //detect abnormalities in the list (broken links) after n (if any)
  while(after && tmp)
  {
    if ((after->prev != tmp) || (tmp->next != after))
    {
      brokenlinks++;
    }
 
    after = after->next;
    tmp = tmp->next;
  }
 
  //detect abnormalities in the list (broken links) before n (if any)
  tmp = n;
  while(before && tmp)
  {
    if ((before->next != tmp) || (tmp->prev != before))
    {
      brokenlinks++;
    }
 
    before = before->prev;
    tmp = tmp->prev;
  }
 
  return brokenlinks;
}

any suggestions?

Popularity: 15%

The following program doesn’t "seem" to print "hello-out".  What is
the reason behind it?

#include <stdio.h>
#include <unistd.h>
int main()
{
    while(1)
    {
        fprintf(stdout,"hello-out");
        fprintf(stderr,"hello-err");
        sleep(1);
    }
    return 0;
}

When you observe, it looks as if the program prints only "hello-err".
But then, all of sudden, it prints "hello-out" in a bulk!  Why the
program should behave like that when it should print "hello-out" and
"hello-err" in sequence?

If you understand the concept of buffering, you will come know to why
the above program behaves like this.

Streams are of two types:  buffered and unbuffered.  Streams also can
also be categorized as text streams and binary streams.  However, on a
system like UNIX, these are identical.  Text streams that are buffered
are flushed when any of the following conditions are met:

   - The buffer is full
   - When ‘\n’ is encounterd, if the stream is line buffered
   - When a function to read from stdin is invoked
   - When the program exits
   - If the default flushing behaviour is modified by the setvbuf(3)
     library function.

Whereas, unbufferd stream are flushed as soon as the data arrive.
stderr is unbuffered by default, because this stream is used for error
reporting, and error reporting should not be delayed by buffering.

Run the above program without change and see that after some time
"hello-out" is printed in bulk.  stdout is line buffered, so if you
replace the above

    fprintf(stdout,"hello-out");

with

    fprintf(stdout,"hello-out\n");

"hello-out" is printed in iteration.

To know more on streams, refer K&R-II, section B.1.

Popularity: 5%

Here is the routine for reversing single linked list using a stack, for reversing linked list using pointers, see the earlier post. For reversing linked list recursively visit this post. This routine takes a single linked list as argument and reverse it and returns back the head node to the reversed list.

 
struct Node *reverse(struct Node* node)
{
  struct Node *tmpnode, *headnode;
 
  Stack *stack = CreateStack();
 
  while(node)
  {
    Push(stack, node);
    node = node->next;
  }
 
  headnode = Pop(stack);
  tmpnode = node = headnode;
 
  while(tmpnode)
  {
    tmpnode = Pop(stack);
    node->next = tmpnode;
    node = node->next;
  }
 
  DestroyStack(stack);
  return headnode; 
}

comments welcome…

Popularity: 48%

Here is the routine for reversing single linked list recursively, for reversing iteratively see the earlier post . For reversing circular single linked list visit this post. This routine takes a single linked list as argument and reverse it and returns back the head node to the reversed list.

struct Node *reverse(struct Node* node)
{
  static struct Node *tmpnode = NULL;
  static struct Node *headnode = NULL;

  if (NULL == node)
  {
    return node;
  }

  if (node->next)
  {
    reverse(node->next);
    tmpnode->next = node;
    tmpnode = tmpnode->next;
  }
  else
  {
    headnode = node;
    tmpnode = headnode;
  }

  tmpnode->next = NULL;

  return headnode;

}

comments are always welcome…

Popularity: 92%

This is one of the more simple snippets I could actually write, and one of the best memorized pieces of code that I can actually write as the starting post of this blog. For interested bloggers who would want to be able to post their snippets here, contact me (Dean Michael Berris) through email (see page description for updated email information).

inline bool isprime(unsigned long int number)
{
  if (number <= 3)
    return true;

  if ((number % 2) == 0)
    return false;

  for (unsigned register int i = 5; i * i <= number; i+=2)
  {
    if ((number % i) == 0)
      return false;
  }
  return true;
}

Comments and optimizations most welcome.

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.

Popularity: 5%

The past couple of days, I had been working on a project which requires me to write Java code. OK, I know, this is a C++ blog — this
is my blog after all — but there’s something I’ve picked up a couple of days that I would like to share. I found a few important hints as to
how maybe C++ can get a boost in popularity and usability (or market infiltration). I’ve compiled a short list:

• Libraries!
  We need more libraries. Java thrives because of the libraries and frameworks, and packages, and middle-ware, and other things that make it very rich to use. It doesn’t even allow operator overloading, but writing classes day in and day out over and over again is not fun, which is why people actually pay for libraries and packages.
• A really cool IDE!
  Java has IntelliJ and the Eclipse project which allows developers to write code easily. I believe it’s the age of the short-attention-span-developer (which I admit to being to some extent) where we want instant gratification. I love how ctrl+tab will move to the next word boundary instead of the next space: perhaps before `i’ in `some_idea’ instead of after the `a’. Code folding is great, especially if it’s automatically done for you (and automatic/assisted imports) with a key combination. I’d like to see something better than Microsoft’s Visual C++ IDE (haven’t used others yet, but they are just too expensive for a developer in the Philippines).
• Cool marketing conventions! Java
  developers have more than one excuse to have their company pay for a convention somewhere because Java convention events happen everywhere! When will we have a C++Con, where we hype things up and have Intel, Microsoft, Adobe, (Google maybe?) and other C++ players where people would actually want to go to?
• Teach C++! I’d love to teach high school students how to program in C++ — the same people who would someday want to write their games in C++. Teach the same people who will write the next operating system. Teach the same people who will shape the high performance computing systems and design the next killer application running on the new computer architecture.

These are not very technical issues that we C++ developers can do something about. I’m just personally tired of having to write in a language which I have long never liked because of the restrictions. Java is very rich and the developer community is very lively but I like my multi-paradigm programming because it just works right for my brain.

I learned Java before I even learned C++ — and I’ve never gone back on my preference, because I feel much more productive in C++ than in Java. Yes, demand is high for Java development and our company is filling a niche in the Philippines (high-level Java training and software architecture).

Having said how Java is very successful marketing wise, I guess there are some technical issues that seem to have merit based on the Java design. Here are a few things that other languages have that C++ don’t which might be very interesting to see in the future:

• Portable Bytecode is a very interesting concept. Perhaps we can use a single bytecode compiler from standard C++ code and just "distill" that for the target platform. Nope, I don’t like the idea of the VM/Interpreter, but I like the idea of a common bytecode.
• Standard ABI might be harder to pull off, but if Microsoft starts by implementing a single Application Binary Interface — they’ve already done this with .NET and CLR, but they still have an interpreter/runtime embedded in the OS — then perhaps other operating systems will follow suit. To simplify (which I think is bordering on another anti-trust lawsuit if MS does implement this): "your compiled code should only look like this so that it works with everything else".
• Free Standard C++ Compiler which implements the whole standard and works on all supported platforms and produces a Portable Bytecode and implements the Standard ABI. This is what made Java successful, because in the beginning only one compiler and interpreter was available — which practically gave them complete control over the language. Perhaps if Microsoft implemented a C++ compiler on all imaginable platforms instead of just implementing for their platform, perhaps they’d have a control that Sun
  has on the Java language. Maybe the GNU C++ compiler might be a good candidate, but a lot of people (like me) get burnt on non-Linux/Unix platforms with it that it just doesn’t feel right to use them on other platforms aside from Linux/Unix.

Consider this a wish list, but it’s more a suggestion list — or a call to other developers who can do something about it — for the people in position who have the capability to do something about the C++ proliferation and C++ marketing. I feel passionate about this because I feel C++ has so much more to offer as a programming language than just the traditional object oriented C that people get taught and keep hearing about.

I hope someday I can do something about this in a bigger way.

by Dean Michael

This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.

Popularity: 4%

Here is the code snippet which does conversion from unsigned long long (uint64) to
string/ascii/char *. 

it takes input as unsigned long long (uint64), converts it to string, it takes care of the base also.

example usage of function ulltostr is: ulltostr(1023234343453553, ptr, 10);

here is the code snippet….

 
#include <stdio.h>
 
#ifdef _MSC_VER
typedef unsigned __int64 uint64;
#else
typedef unsigned long long uint64
#endif
 
char *ulltostr(uint64 value, char *ptr, int base)
{
  uint64 t = 0, res = 0;
  uint64 tmp = value;
  int count = 0;
 
  if (NULL == ptr)
  {
    return NULL;
  }
 
  if (tmp == 0)
  {
    count++;
  }
 
  while(tmp > 0)
  {
    tmp = tmp/base;
    count++;
  }
 
  ptr += count;
 
  *ptr = '\0';
 
  do
  {
    res = value - base * (t = value / base);
    if (res < 10)
    {
      * - -ptr = '0' + res;
    }
    else if ((res >= 10) && (res < 16))
    {
        * - - ptr = 'A' - 10 + res;
    }
  } while ((value = t) != 0);
 
  return(ptr);
}

please post your comments and suggestion if any….

Popularity: 12%

There are three important differences between ANSI C and K&R C:

• The first feature is the prototype - writing the parameter types as a part of the function declaration.  Prototypes make it easy for a compiler to check function use with definition.
   
• Second feature is the addition of new keywords -
• enum for enumerated types
• const
• volatile
• signed
• void

And the ‘entry’ keyword was retired.

• Third category is of "silent changes" - some features that still compiles, but now has a slightly different meaning.  For example, now that the preprocessing rules are more tightly defined, there’s a new rule that adjacent string literals are concatenated.

Popularity: 4%

Did you know that the following if statement is semantically right, but could logically be wrong?

    if ( i = 2 )
    {
        /* do something */
    }   

Tip:

The compiler may only produce a waring: "Possibly incorrect assignment", but we may ignore it.  To avoid such a mistake, just reverse the two identifiers.

    if ( 2 == i )
    {
        /* do something */
    }

If ‘==’ is replaced by an ‘=’, the compiler will give an error saying "Lvalue required".

Note:  This post is just to provide a hint and may not suit to your coding style.

Popularity: 4%