Reversing a linked list

Copyright Donovan Rebbechi 2001. This tutorial may be distributed freely if this copyright notice is preserved. Changes require authors permission. The code is no-strings attached free software, it may be redistributed, modified, and used.

template
class List
{
public:
struct Node
{
Node(const T& data, Node* next=0):data(data),next(next) {}
Node* next;
T data;
};

List() : head(0) {}

Node* begin() { return head; }
Node* end() { return 0; }

void reverse()
{
Node* p = 0; Node* i = begin(); Node* n;
while (i)
{
n = i->next; //This saves the address of the next node
i->next = p;//// make the next pointer point to previous node
p = i; //// update previous node to point to “current”
i = n;// recall the address of the node after i
}
head = p;
}
private:
Node* head;
};

To reverse the list, we need to traverse the list, and modify the next pointer of each node, so it points to the previous node.

Circular lists: A circular list is a linked list that has the property that the last node in the list contains the address of the first node.

Advertisements

XOR

http://www.javamex.com/java_equivalents/unsigned.shtml

This post is motivated by an interesting article posted above.

Also interesting uses of XOR can be found in the form of XOR swap (no-temp-swap) and XOR linked list (Doubly linked list with a single variable to store both the prev and next pointers)

Following properties of XOR are what makes it very powerful –

X^X=O (Zero) – common sense (a value xor’d with itself is bound to be zero)

X^O = X = identity

X^Y = Y^X  = Reflexivity

X^(Y^Z) = (X^Y)^Z = transitivity

libcurl

http://curl.netmirror.org/libcurl/c/libcurl-tutorial.html

C/C++ – Resources

http://www.informit.com/content/images/art_deitel_pointer/elementLinks/ptrarithmatic.pdf – By Deitel

http://publications.gbdirect.co.uk/c_book/the_c_book.pdf – I have not read this myself 🙂

http://www.informit.com/authors/bio.aspx?a=e19aded6-574c-4c46-8511-101f9f0ed8f8 – Danny Kalev’s blog. Very informative.

http://www.informit.com/guides/guide.aspx?g=cplusplus – C++ Reference

Dr. Dobb’s