Home » Blogs » vishnu's blog

A Nice C++ Linked List

I had reason to brush up on my C/C++ skills a bit and did something I've wanted to do for some time: implemented a nice encapsulated linked list. Read more for the source. 

#include <iostream>
#include <stdarg.h>

typedef unsigned char boolean;

class LinkedList {
  
  private:
    LinkedList *m_start, *m_curr, *m_next;
    int m_data;
  
  public:    
    /*Constructors*/
    LinkedList();
    LinkedList(LinkedList* );
    
    /*Operations*/
    void insert(int);   
    void insertMultiple(int count, ...);  
    int getData();
    int getDataEl();
    void setData(int);
    LinkedList* getNext();
    void setNext(LinkedList* );

    
    /*Movement*/
    void start();
    void next();
    void end();        
    void reset();
    
    /*Boolean*/
    boolean isEnd();
    boolean isEmpty();
    
};


LinkedList::LinkedList() {
  m_curr = m_start = this;
  m_next = NULL;
}

LinkedList::LinkedList(LinkedList* start) {
  m_start = start;
  m_next = NULL;
}

void LinkedList::insert(int el) {
  m_curr->setData(el);
  m_curr->setNext(new LinkedList(m_start)); 
  m_curr = m_curr->getNext(); 
}

void LinkedList::insertMultiple(int count, ...) {
  va_list ap;
  va_start(ap, count);
  while(count--)     
    insert(va_arg(ap, int)); 
  va_end(ap);
}

int LinkedList::getDataEl() {
  return m_data;
}

int LinkedList::getData() {
  return m_curr->getDataEl();
}

void LinkedList::setData(int el) {
  m_data = el;
}

LinkedList* LinkedList::getNext() {
  return m_next;
}

void LinkedList::setNext(LinkedList* link) {
  m_next = link;
}

void LinkedList::next() {
  m_curr = m_curr->getNext();
}

boolean LinkedList::isEnd() {
  return m_curr->getNext() == NULL ? 1 : 0;
}

void LinkedList::reset() {
  m_curr = m_start;
}

int main() {
  LinkedList l;
  l.insertMultiple(3, 5, 6, 7); 
  for(l.reset(); !l.isEnd(); l.next()) 
    std::cout << l.getData();
    
  return 0;
}
Here's a doubly linked list version: 


#include <iostream>
#include <stdarg.h>

typedef unsigned char boolean;

class LinkedList {
  
  private:
    LinkedList *m_curr, *m_next, *m_prev;
    int m_data;
  
  public:    
    /*Constructors*/
    LinkedList();
    LinkedList(LinkedList* );
    
    /*Operations*/
    void insert(int);   
    void insertMultiple(int count, ...);  

    /*Get Setters*/
    int getData();
    int getDataEl();
    void setData(int);
    LinkedList* getPrev();
    LinkedList* getNext();
    void setNext(LinkedList* );        
    
    /*Movement*/
    void reset();
    void prev();
    void next();
    void end();           
    
    /*Boolean*/
    boolean isBeginning();
    boolean isEnd();
    boolean isEmpty();
    
};


LinkedList::LinkedList() {
  m_curr = this;
  m_prev = NULL;
  m_next = NULL;
}

LinkedList::LinkedList(LinkedList* prev) {
  m_prev = prev;
  m_next = NULL;
}

void LinkedList::insert(int el) {
  while (m_curr->getNext() != NULL)
    m_curr = m_curr->getNext();
  m_curr->setData(el);
  m_curr->setNext(new LinkedList(m_curr));
}

void LinkedList::insertMultiple(int count, ...) {
  va_list ap;
  va_start(ap, count);
  while(count--)     
    insert(va_arg(ap, int)); 
  va_end(ap);
}

int LinkedList::getDataEl() {
  return m_data;
}

int LinkedList::getData() {
  return m_curr->getDataEl();
}

void LinkedList::setData(int el) {
  m_data = el;
}

LinkedList* LinkedList::getPrev() {
  return m_prev;
}

LinkedList* LinkedList::getNext() {
  return m_next;
}

void LinkedList::setNext(LinkedList* link) {
  m_next = link;
}

void LinkedList::reset() {
  m_curr = this;
}

void LinkedList::next() {
  m_curr = m_curr->getNext();
}

void LinkedList::prev() {
  m_curr = m_curr->getPrev();
}

boolean LinkedList::isEnd() {
  return m_curr->getNext() == NULL ? 1 : 0;
}

boolean LinkedList::isBeginning() {
  return m_curr == NULL ? 1 : 0;
}

boolean LinkedList::isEmpty() {
  return m_curr->getNext() == m_curr->getPrev() ? 1 : 0;
}

int main() {
  LinkedList l;
  l.insertMultiple(4, 5, 6, 7, 8); 

  for(; !l.isBeginning(); l.prev())
    std::cout << l.getData();
   
  return 0;
}
By vishnu on 2006-03-04
Don't copy this, use std::list instead
Submitted by MaHuJa (not verified) on Thu, 2007-12-06 16:16.
This is something that you can (and I guess should) make for the sake of practice, but I've seen people copy that code off here and use it in their own app. I'd recommend they rather use std::list which is included in the standard library of every compiler. The differences can be summarized like this:
  • Digging through the internals of std::List is more difficult. Looking at this implementation can be useful for understanding how Linked Lists work.
  • The std::list iterator comes as its own (sub) class, not integrated.
  • std::List is based on templates, making it far more reusable - but to use it requires a very slight bit of additional knowledge.
Example usage of std::list - this will do exactly the same as his code: 
#include <iostream>
#include <list>
using std::list;

int main() {
  list<int> l;
  l.push_back(3);
  l.push_back(5);
  l.push_back(6);
  l.push_back(7);  // push_back puts it at the end

  list<int>::iterator iter;


  for(iter = l.begin(); iter != l.end(); iter++) 
    std::cout << *iter;  //Iterators work similarly to pointers

  return 0;
}
See also the other standard library container classes, like vector.