11/8/12

Data structures: the List (where arrays have no meaning and your whole life is a lie)


This time, an intuitive structure with a not so intuitive implementation, the list.

What is a list?
A list is an array of elements put in a distinct order, but that can have new elements introduced in between any other two elements, as well as deleting any element in any position. This helps us in not having a fixed structure in which an error while introducing elements can cost us a lot of time and resources to fix.




Therefore, we may need to be able to go through all the elements in the list in order to check, add, or delete any elements. To do that, however, it may be wise to also create an iterator, that is, a pointer that may be able to automatically do such search.

What can you do with a list?

  • Create: begin the list data structure, reserve space.
  • Add: put a new element. Where, however? If we point at an existing element of the list (which is all we can do), do we add the new element before, or after him? And how do we do it to ensure there's capacity for it, and that we do not need to sacrifice too many resources on resizing the list?
  • Delete: remove the element at the specified position.
  • Alter: change the value in the element
  • Value: get the value of the element
  • First: get the first element.
  • Size: gives the number of listed objects
  • Empty: checks whether the list has no elements.
Advantages
  • Extremely flexible: adding, deleting, altering or checking any element, any position.
  • Convenient use of an iterator
Setbacks
  • Tougher implementation: arrays do not work as a storing base.
  • Hardly scalable: worst case scenario, your adding, deleting, altering or checking elements will cost you to go through all the list.

We've all done a list at some point in our life. Having our affairs in order, striking out what we've accomplished, adding new objectives or modifying them. All in all it's a good way to store data so long as it's more of an impromptu or small storage; because a list that grows too big becomes harder and harder to keep track of. With that in mind, we can deduce in which contexts a list is useful.

Implementation: how the buck are we gonna do this?
Having the list modify elements in the middle of the structure means using arrays or simple storages will elevate the cost of the actions dangerously. Every new item will mean rearranging the whole thing. So how do we do it?

Pointers. And magic.

Each element of a list will contain its information and a pointer to the next element, creating a chain of elements. We will only need to have a pointer to the first element; from there we can access the pointers of the elements to advance through the list.

We will also need a Ghost Element. It will be a flagged element which is not valuable, but has a functionality.



It will always be at the end of the list. By adding/deleting elements before a certain element, we will be able to put an element everywhere but at the end of the list. However, with the Ghost, we can add an element before him, effectively putting an element at the end of the usable list.

It is very important that the users can't alter the Ghost.

/*
 * list.h
 *
 *  Created on: 29/06/2012
 *      Author: Daniel
 *
 *      This snippet of code is free to use
 */

#include <iostream>
#include <stdlib.h>

#ifndef LIST_H_
#define LIST_H_

template<typename T>
class ListEl { //Elements that go into the list

private:
    T* _element; //Actual information
    ListEl<T>* _next; //Pointer to the next eListEl

public:
    ListEl() {
        _element = NULL;
        _next = NULL;
    }

    ListEl(T input) {
        _element = new T();
        *_element = input;
        _next = NULL;
    }

    T getElement() {
        return *_element;
    }
    void setElement(T in) {
        _element = new T();
        *_element = in;
    }
    ListEl* getPointed() {
        return _next;
    }

    bool pointTo(ListEl* obj) { //We retain the direction, not the element, for versatility; else we'd be playing a game of russian dolls.
        if (obj != NULL) { //little failsafe to ensure the ListEl exists and we're not being fed null stuff.
            _next = obj;
            return true;
        }
        std::cout << "Error at pointTo, object is null";
        return false;
    }

    void clear(){
        _element = new T();
        _next = NULL;
    }
};

//------------------------------------------------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------------------------------------------------

//------------------------------------------------------------------------------------------------------------------------------------------

template<typename T>
class List {

private:
    ListEl<T> *_first; //first element, pointer needed to run through the list
    T _flag; //Value that will describe the ghost element. giggle at the ghosties...
    int _size;
    ListEl<T> *it; //iterator

public:
    List(T flag) { //first
        _first = new ListEl<T>(flag); //ghost points nowhere -> danger!
        _flag = flag;
        _size = 0; //we don't count the ghost.
        it = _first;
    }

    bool isEmpty() {
        if (_size > 0) {
            return false;
        }
        return true;
    }

    ListEl<T> getItem() {
        if (it->getElement() != _flag) {
            return *it;
        } else {
            std::cout << "Empty list";
            return NULL;
        }
    }

    void first() {
        it = _first;
    }

    void alter(T value) {
        it->setElement(value);
    }

    void erase() {

        if (!isEmpty()) {

            it->setElement(it->getPointed()->getElement()); //copy the next element
            it->pointTo(it->getPointed()->getPointed());//the element in the middle will now be nowhere

            _size--;

            it->getPointed()->clear(); //free memory
        }else{
            std::cout << "Can't erase - list is empty";
        }
    }

    void next() {
        if (it->getPointed()->getElement() != _flag) {
            it = it->getPointed();
        } else { //if the next is the ghost, we're at the end!
            std::cout << "End of list";
        }
    }

    bool add(T value) { //we could ask for a ListEl, but it's more comfortable for the programmer if they just need to input the value.
        ListEl<T> *laux = new ListEl<T>(); //an empty node...

        if (!isEmpty()) { //so long it's not the ghost (points SOMEWHERE...)
            laux->pointTo(it->getPointed()); //we copy there the current node...
        }
        laux->setElement(it->getElement()); //so laux is the current node...

        it->pointTo(laux); //and the old current node points to laux, putting it BEFORE him...
        it->setElement(value); //and we have added a node BEFORE! tough to wrap your head around it the first time.
        _size++;

        return false;
    }

};

#endif /* LIST_H_ */

------

Left as an exercise is devise a find() function that will tell you the index of the element you query.

Next up, trees.

1 comentario: