間接アドレスベースのリニア・テーブル

シーケンスストレージ構造の線形テーブルでは、要素を追加または削除する際に大量のデータを移動する(平均n/2回移動する)という著しい欠陥があり、各要素が占有する空間が大きい場合、効率が低い.間接アドレスは、この問題を解決するためのソリューションです.
間接アドレスの考え方は,順序記憶構造に基づいて,各要素がデータのアドレスを格納し,増加または削除時にアドレスを移動するだけで,要素が大きくテーブル長が大きい場合,効率の向上が期待できるということである.
C++言語のコードは以下のように実現される.

/**
 *                 
 */

#pragma once
template < class T >
class List
{
public:
    List(int c = 10);
    ~List(void);
    int getLength();
    int getCapacity();
    bool isEmpty();
    T getData(int index);
    void addData(T t);
    void addData(T t, int index);
    T deleteData(int index);
    void clear();
    void print();
private:
    int len;
    int capacity;
    T **data;
    void ready();
    void arrayCopy(T **dst, int dstStart, T **src, int srcStart, int n);
};

template < class T >
List< T >::List(int c)
{
    capacity = (c >= 0 ? c : 0);
    len = 0;
    if (capacity > 0)
    {
        data = new T*[capacity];
    }
}

template < class T >
List< T >::~List(void)
{
    for (int i = 0; i < len; i++)
    {
        delete data[i];
    }
    delete data;
}

/**
 *     ，           
 */
template < class T >
void List< T >::clear()
{
    for (int i = 0; i < len; i++)
    {
        delete data[i];
    }
    delete data;
    this();
}

template < class T >
int List< T >::getLength()
{
    return len;
}

template < class T >
int List< T >::getCapacity()
{
    return capacity;
}

template < class T >
bool List< T >::isEmpty()
{
    return (len == 0);
}

template < class T >
T List< T >::getData(int index)
{
    if (index < 0 || index >= len)
    {
        return NULL;
    }
    return *data[index];
}

/*
 *         ，      ，     
 */
template < class T >
void List< T >::ready()
{
    if (len >= capacity)
    {
        if (capacity == 0)
        {
            capacity = 10;
            data = new T *[capacity];
        }
        else
        {
            T **newData = new T*[capacity * 2];
            arrayCopy(newData, 0, data, 0, capacity);
            delete data;
            data = newData;
            capacity *= 2;
        }
    }
}

/**
 *    src n      dst 
 */
template < class T >
void List< T >::arrayCopy(T **dst, int dstStart, T **src, int srcStart, int n)
{
    for (int i = 0; i < n; i++)
    {
        dst[dstStart + i] = src[srcStart + i];
    }
}

/**
 *         
 */
template < class T >
void List< T >::addData(T t)
{
    addData(t, len);
}

/**
 *           
 */
template < class T >
void List< T >::addData(T t, int index)
{
    if (index < 0 || index > len)
    {
        return;
    }
    ready();
    for (int i = len - 1; i >= index; i--)
    {
        data[i + 1] = data[i];
    }
    data[index] = new T(t);
    len++;
}

/**
 *          
 */
template < class T >
T List< T >::deleteData(int index)
{
    if (index < 0 || index >= len)
    {
        return NULL;
    }
    T temp = *data[index];
    delete data[index];
    for (int i = index + 1; i < len; i++)
    {
        data[i - 1] = data[i];
    }
    len--;
    return temp;
}

/**
 *         ，     
 */
template < class T >
void List< T >::print()
{
    cout << "----" << endl;
    for (int i = 0; i < len; i++)
    {
        cout << *data[i] << endl;
    }
}