Tell me more ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 3 down vote favorite

TO DO

  • exception handling
  • merge with dynamic arrary

*SO Bug here--remove this line and Control K will not work

/* 
Added in comments from Jerry, Ed and Loki 
This code borrows from from http://cslibrary.stanford.edu/    
C++ Version - lnode, lnode_reverse, lnode_push, lnode_print, lnode_count 
*/
#include "c_arclib.cpp"
template <class T1> class sl_list
  {
  private:
    class node_1 
      {
      public:     
        T1 data; 
        node_1 *next;
        node_1(T1 data, node_1 *next = NULL) : data(data), next(next) {}        
      };
    node_1 *head;
    int count;
  public:
    sl_list() : count(0), head(NULL){}
    void push(int data) 
      {
      node_1 *newNode = new node_1(data, head); 
      ++count; 
      head = newNode;
      }
    void print() 
      {
      node_1 *current=head;
      while (current != NULL) 
        {
        cout << current->data << endl;
        current = current->next;
        }
      }
    void reverse()
      {
      node_1 *previous, *current, *future;
      previous=NULL;
      current=head;
      future=head;
      while(current!=NULL)
        {
        future=current->next;
        current->next=previous;
        previous=current;
        current=future;
        }
      head=previous;
      }
    void break_heap()
      {
      int i=0;
      while(1)
        {
        i++;
        push(1);
        }
      }
    };
/*
C Version - lnode, lnode_reverse, lnode_push, lnode_print, lnode_count
*/

typedef struct node_type 
  { 
  int data; 
  struct node_type* next; 
  } lnode_type;

struct lnode 
  {
  int data;
  struct lnode* next;
  };
void lnode_reverse(struct lnode*& head)
  {
  struct lnode *previous, *current, *future;
  previous=NULL;
  current=head;
  future=head;
  while(current!=NULL)
    {
    future=current->next;
    current->next=previous;
    previous=current;
    current=future;
    }
  head=previous;
  }
void lnode_push(struct lnode*& head, int data) 
  {
  struct lnode* newNode = new lnode; 
  newNode->data = data;
  newNode->next = head;
  head = newNode; 
  }
void lnode_print(struct lnode* current) 
  {  
  while (current != NULL) 
    {
    cout << current->data;
    current = current->next;
    }
  }
int lnode_count(struct lnode* current) 
  {
  int count = 0;
  while (current != NULL) 
    {
    count++;
    current = current->next;
    }
  return count;
  } 
void break_heap()
  {
  struct lnode* head = NULL;
  int i=0;
  while(1)
    {
    i++;
    lnode_push(head,1);
    }
  }
int main()
  {
  sl_list<int> list1;
  list1.push(10);
  list1.push(20);
  list1.push(30);
  list1.push(40);
  list1.push(50);
  list1.push(60);

  list1.print();
  list1.reverse();
  list1.print();
  }
share|improve this question
what's the break_heap method for? It sounds malicious and it's public too! – greatwolf Nov 3 '11 at 7:48

1 Answer

up vote 5 down vote accepted 
/* C++ Version - lnode, lnode_reverse, lnode_push, lnode_print, lnode_count
   I need node_type turned into a templated class..How does one do this?
*/
typedef struct node_type 
  { 
  int data; 
  struct node_type* next; 
  } lnode_type;

Turning it into a template is pretty straightforward:

template <class T>
class node_type { 
   T data;
   node_type *next;
};

Note that the typedef isn't really necessary (or desirable) in C++. You normally just want to use class whatever, and then the body of the class definition. This makes whatever usable as a name by itself, just about like the typedef would in C.

There's one other thing we probably want to do though: the whole basic idea of a linked-list node is really just an implementation detail of the linked list, so we really want to make the node type a nested class inside of the linked-list class:

template <class T>
class sl_list {

    struct node {
        T data;
        node *next;
    } head;

public:
    // Other stuff here.
};

From there, we want to write the functions that work with the data type to use T instead of int. For example, instead of your push(int), you might write something like this:

void push(T data) {
  ++count; // prefer pre-increment when you don't need the old value.
  node* newNode = new node; 
  newNode->data = data;
  newNode->next = head;
  head = newNode; 
}

We might prefer to add a ctor to the node class/struct, something like this:

node(T data, node *next = NULL) : data(data), next(next) {}

With that, push becomes something like this:

void push(T data) { 
    node *newNode = new node(data, head);
    ++count;
    head = newNode;
}

[Edit2: Note that, as recommended by @LokiAstari, I've also moved the ++count to after allocating the new node. This way if the attempted allocation fails (and new throws an exception), count will not be incremented, so it retains the correct values. If and only if the allocation succeeds, it's incremented to reflect the new node having been added to the list. ]

[Edit: and node would look roughly like this:

    struct node {
        T data;
        node *next;

        node(T data, node *next = NULL) : data(data), next(next) {}            
    } head;

]

share|improve this answer
Thanks...everything made sense except these lines: We might prefer to add a ctor to the node class/struct, something like this: node(T data, node *next = NULL) : data(data), next(next) {} – Hiro Protagonist Nov 1 '11 at 4:09
3  
The one thing I would add is exception safety. No operation that modify the object should be performed until all exception dangerous code has completed. Thus in push(), the ++count should be moved after the call to new. If new throw the state of the object is left in an inconsistent state. – Loki Astari Nov 1 '11 at 12:33
@LokiAstari: Good point. Done. – Jerry Coffin Nov 1 '11 at 13:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.