OSDev.org

Code: Select all

class Node{
    friend class Iterator;
    friend class List;
    Node* next;
    type data;
}

class List, etc.
class Iterator, etc.

Code: Select all

template<typename T>
class Node {
    friend class Iterator;
    friend class List;
    Node * next;
    T data;
};

Code: Select all

object* get_obj(){ return some_pointer; }

Code: Select all

class Node{
    protected:
         Node* next;
         type data;
};
class List:public Node{
    private:
         Node* head;
};

Code: Select all

class Node{
    Node* next;
    type data;
    friend class List;
};
class List{
    private:
        Node* head;
};

Code: Select all

template <typename T>
class list {
    class entry {
      public:
        T item;
        entry *next, *prev;
    };
    entry *head, *tail;
public:
    // interface
};

Code: Select all

/***************************************************************************\
 * The Mattise Kernel														*
 * Copyright 2007 Matthew Iselin											*
 * Licensed under the GPL													*
 *																			*
 * LinkedList.hpp															*
 *																			*
 * Easy-to-use linked list class for any type.								*
 *																			*
\***************************************************************************/

//--------------- Includes ---------------//

// These are dependent on your system...

#include <iostream>
#include <stdio.h>

//--------------- Class Definition ---------------//

/**
	The CLinkedList class basically is a shell around a certain data
	type. It allows linked lists to be created for any data type,
	hence saving coding time.
**/

// main class
template< class _T > class CLinkedList
{
	public:

		// initializes the list
		CLinkedList();

		// destroys all data in the list
		~CLinkedList();

		// dumps the list
		void Dump();

		// clears the list
		void Clear();

		// inserts data at the given offset, shifting everything else
		int Insert( _T, int );

		// pushes data onto the end of the list
		int Push( _T );

		// pops data off the end of the list
		_T Pop();

		// gets data from the list
		_T Get( int );

		// deletes an item
		void Delete( int );
		
		// retrieves the size
		int Size();
		
		// gets data using a random-access operator
		_T operator [] ( int i );

	private:

		// the list type
		struct myType
		{
			_T data;
			struct myType* next;
			struct myType* prev;
		};

		// the start of the list
		struct myType start;
		
		// size of the list
		int size;
};

template< class _T > CLinkedList<_T>::CLinkedList()
{
	// set the next and prev fields of start to null
	start.next = start.prev = (struct myType*) NULL;
	
	// there are no elements yet
	size = 0;
}

template< class _T > CLinkedList<_T>::~CLinkedList()
{
	// clear the list, free the memory
	Clear();
}

template< class _T > int CLinkedList<_T>::Size()
{
	// return the size
	return size;
}

template< class _T > void CLinkedList<_T>::Dump()
{
	// iterate through the list, displaying information about each item

	// running pointer
	struct myType* curr = start.next;

	// running accumulator
	unsigned int i = 0;

	// dump each item
	while( curr != (struct myType*) NULL )
	{
		// print it - this may not be a really good idea :D
		cout << "LIST[" << i++ << "]: " << curr->data << endl;

		// get the next pointer
		curr = curr->next;
	}
}

template< class _T > int CLinkedList<_T>::Push( _T d )
{
	// find the end of the list, then append the data

	// running pointers
	struct myType* prev, *curr = &start;

	// wait until curr is null
	while( curr != (struct myType*) NULL )
	{
		// save the current pointer
		prev = curr;

		// load the next one
		curr = curr->next;
	}

	// check that the one we want to add to isn't null
	if( prev == (struct myType*) NULL )
	{
		// fail!
		return -1;
	}

	// safe, so append - we need to make a structure first
	struct myType* m = (struct myType*) malloc( sizeof( struct myType ) );
	m->prev = prev;
	m->next = (struct myType*) NULL;
	m->data = d;

	// fill it in
	prev->next = m;
	
	// one more element
	size++;

	// success!
	return size-1;
}

template< class _T > _T CLinkedList<_T>::Pop()
{
	// find the end of the list, and remove it after saving its data

	// running pointers
	struct myType* prev, *curr = &start;

	// wait until curr is null
	while( curr != (struct myType*) NULL )
	{
		// save the current pointer
		prev = curr;

		// load the next one
		curr = curr->next;
	}

	// check that prev isn't null
	if( prev == (struct myType*) NULL )
	{
		// return start's data
		return start.data;
	}

	// prev holds the data we want
	_T ret = prev->data;

	// now unlink prev (the previous one's next is NULL)
	prev->prev->next = (struct myType*) NULL;

	// and free the pointer
	free( prev );
	
	// one less element
	size--;

	// return the data
	return ret;
}

template< class _T > _T CLinkedList<_T>::Get( int offset )
{
	// loop through the list until we hit either NULL or the offset

	// offset into the list
	int o = 0;

	// running pointer
	struct myType* curr = start.next;

	// keep on going
	while( o++ != offset && curr != (struct myType*) NULL )
		curr = curr->next;

	// we've hit the offset or NULL
	if( curr == (struct myType*) NULL )
		return start.data;

	// return the data
	return curr->data;
}

template< class _T > void CLinkedList<_T>::Delete( int offset )
{
	// loop through the list until we hit either NULL or the offset
	// then unlink it

	// offset into the list
	int o = 0;

	// running pointer
	struct myType* curr = start.next;

	// keep on going
	while( o++ != offset && curr != (struct myType*) NULL )
		curr = curr->next;

	// we've hit the offset or NULL
	if( curr == (struct myType*) NULL )
		return;

	// unlink the item
	if( curr->prev )
		curr->prev->next = curr->next;
	if( curr->next )
		curr->next->prev = curr->prev;
	
	// one less element
	size--;

	// free the memory
	free( curr );
}

template< class _T > int CLinkedList<_T>::Insert( _T d, int offset )
{
	// loop through the list until we hit either NULL or the offset
	// then append data to it

	// offset into the list
	int o = 0;

	// running pointer
	struct myType* curr = start.next;

	// keep on going
	while( o++ != offset && curr != (struct myType*) NULL )
		curr = curr->next;

	// we've hit the offset or NULL
	if( curr == (struct myType*) NULL )
		return -1;

	// create a new item
	struct myType* m = (struct myType*) malloc( sizeof( struct myType ) );
	m->data = d;
	m->next = curr->next;
	m->prev = curr;

	// link it into the list
	curr->next = m;
	
	// one more element
	size++;

	// success!
	return 0;
}

template< class _T > void CLinkedList<_T>::Clear()
{
	// iterate through the list, freeing memory as we go

	// running pointers - never start at 'start' because it isn't heap allocated
	struct myType* savnext, *curr = start.next;

	// delete each item
	while( curr != (struct myType*) NULL )
	{
		// save this one's next
		savnext = curr->next;

		// delete this one
		kfree( curr );

		// get the next pointer
		curr = savnext;
	}

	// and make sure start is setup properly
	start.next = (struct myType*) NULL;
	start.prev = (struct myType*) NULL;
	
	// there are no elements
	size = 0;
}

template< class _T > _T CLinkedList<_T>::operator [] ( int i )
{
	return Get( i );
}

Code: Select all

template <typename T> class SList{
    
    public:
        
        SList() : head(0) {}
        
        /*
        Slist(const Slist& src);
       ~Slist();
        
        void pushFront(int);
        void pushBack(int);
        void popFront();
        void popBack();
        void insert();
        void remove();
        T retrieve(int);
        int search(T);
        */
        
    private:
        
        class Node{
            
            int id;
            T data;
            Node *next;
            Node(Node* init) : next(init) {}
            Node(T _dat) : next(0), data(_dat) { assign(); }
            
            void assign(){ this->id = 0; } // This func obviously not written yet
        };
        
        Node *head;
};

Code: Select all

void push_front(const T&);  // ?????????