[JackOfAllTrades]

Data Structures covered so far:

An In-Depth Look At Linked Lists
An In-Depth Look At Binary Search Trees
An In-Depth Look at Hash Tables
An Application of Suffix Arrays (in Java, but highly relevant)
An In-Depth Look at Binary Heaps
An In-Depth Look At Huffman Encoding
An In-Depth Look At AVL Trees Part I
An In-Depth Look At AVL Trees Part II
An In-Depth Look At Tries
An In-Depth Look At Radix Trees




Original Post by JackOfAllTrades:
The brilliant KYA has created an outstanding treatise on linked list processing in C++.

If you're learning linked lists and are finding it daunting, then YOU MUST READ THIS BLOG ENTRY!!! It's EVEN. GOT. PICTURES!

*NickDMax Edit: fixed link

This post has been edited by KYA: 01 April 2017 - 05:01 PM

[Mowgef]

I love pictures.

[nathanpc]

Mowgef, on 24 Nov, 2009 - 06:24 PM, said:

I love pictures.

I too!

[KYA]

Updated the original post with the latest and greatest entry: An In-Depth Look At Binary Search Trees

[Bench]

It recently occurred to me that the introduction of shared_ptr to the standard library has the potential to make these learning exercises more accessible, moving the focus away from explicit memory management (and other rules/idioms which go along with them such as Rule of 3 and RAII); instead the focus stays firmly on to data structures themselves as way to understand the high level concepts at least

#include <memory>
struct node;
typedef std::tr1::shared_ptr<node> ptr_t;

struct node
{
    int data;
    ptr_t next;
    node(int d, ptr_t n) 
        : data(d), next(n) {}
}; 

class Stack
{
    ptr_t head;
    Stack(const Stack&) {}   //Unfortunately not copyable
    Stack& operator=(const Stack&) {}
public:
    Stack () {}
    void push(const int& obj) 
    { 
        head.reset(new node(obj, head)); 
    }
    void pop() 
    { 
        head = head->next; 
    }
    bool empty() const 
    { 
        return head == ptr_t(); 
    }
    int& top() const 
    { 
        return head->data; 
    }
}; 

This post has been edited by Bench: 11 December 2009 - 05:07 AM

[Renagado]

Wanted to read those after I saw them a while ago, but the links are broken after we changed to the new server. The new links are:

An In-Depth Look At Linked Lists

An In-Depth Look At Binary Search Trees

Great tutorials btw, thanks KYA.

[KYA]

Thanks for that. [I forgot ] I'll edit the OP.

[KYA]

Updated, now with Hash Tables!

[taylorc8]

Some day, I'm going to be just like KYA.

[kidicarus]

Do you feel that learning data structures in one language, like C++, carries over pretty easily to other languages like Java? Surely a lot of the conceptual aspects of the algorithms do.

[jjl]

object oriented programming is a tricky concept, but once you have grasped that concept then the
transition of OOP to other languages comes with ease. The concept of OOP doesnt vary too much
from language to language

[KYA]

kidicarus, on 24 May 2010 - 02:19 PM, said:

Do you feel that learning data structures in one language, like C++, carries over pretty easily to other languages like Java? Surely a lot of the conceptual aspects of the algorithms do.

Concept is exactly the same, it differs in the fine details (memory management, some syntax, etc...)

[macosxnerd101]

kidicarus, on 24 May 2010 - 05:19 PM, said:

Do you feel that learning data structures in one language, like C++, carries over pretty easily to other languages like Java? Surely a lot of the conceptual aspects of the algorithms do.

If you can do it in C++ and you have a fairly good handle on Java syntax, then you shouldn't have any problem whatsoever implementing your data structure in Java, as you have a lot less to worry about in the lower levels like memory management. If you look at my Linked List Tutorial in Java vs. the Linked List Class snippet in C++, you will see differences beyond basic syntax in implementations for the same concept.

[KYA]

Updated, now with Binary Heaps!

[KYA]

Updated, now with Huffman Encoding!