Key summaries of linked list chapter from Drozdek's Data Structures and Algorithms in C++.
Lists mainly consists of 2 classes, one for node and list for the other. Nodes comprise elements to store and pointers to be linked while List is maintaining the "Head", "Tail" and functions for interface and implementation(e.g., insert, search, etc.).
1. Fundamental lists: singly and doubly linked list.
Nodes of singly linked list has one pointer pointing to the next while doubly linked list contains two pointers. Examples follow by the end of the text.
2. Skip lists and self organising lists.
Skip list is overwhelmingly better in searching with the complexity of lg(n).
self organising lists consist of:
i) move-to-front. (one been searched jumps to the head or tail)
ii) transpose.(one been searched float-up or sink-down by one position)
iii) count (descent by the frequency been searched)
iv) ordering (by certain criterion, e.g., alphabetical)
In terms of efficiency (approximately and regardless of the cost on pointers):
i) == iii) > ii)
i) == iii) > iv)
3. "Two one-dimensional arrays of linked lists" to establish compact index which saves storage space.
#1. class declarations for singly and doubly linked lists.
class IntSingleList
{
public:
IntSingleList() : info(0), next(nullptr) {}
IntSingleList(int in, IntSingleList* pn = nullptr) : info(in), next(pn) {}
int info = 0;
IntSingleList* next;
};
class IntSLList
{
public:
IntSLList() : head(nullptr), tail(nullptr){}
~IntSLList();
int isEmpty()
{
return head == nullptr;
}
void addToHead(int);
void addToTail(int);
int deleteFromHead();
int deleteFromTail();
void deleteNode(int);
bool isInList(int) const;
private:
IntSLLNode* head = nullptr, *tail = nullptr;
};
#2. Example of skip list.
//---------------------------
//skipList.h
const int maxLevel = 4;
template<typename T>
class skipListNode
{
public:
skipListNode() = default;
skipListNode(const T& k, skipListNode *nt = nullptr) : key(k), next(nt){}
T key;
skipListNode *next = nullptr;
};
template<typename T>
class skipList
{
public:
skipList() = default;
bool isEmpty() const;
void choosePowers();
int chooseLevel();
T* skipListSearch(const T&);
void skipListInsert(const T&);
private:
typedef skipList<T> *nodePtr;
nodePtr root[maxLevel] = {nullptr};
int powers[maxLevel] = {0};
};
//----------------------------------
//skipList.cpp
template<class T>
bool skipList<T>::isEmpty() const
{
return root[0] == nullptr;
}
template<class T>
void skipList<T>::choosePowers()
{
powers[maxLevel - 1] = (2 << (maxLevel-1)) - 1; // 2 ^ maxLevel - 1
for (int i = maxLevel - 2, j = 0; i >= 0; --i, ++j)
powers[i] = powers[i+1] - (2 << j); // 2 ^ (j+1)
}
template<class T>
int skipList<T>::chooseLevel()
{
std::default_random_engine e;
int i, r = e() % powers[maxLevel-1] + 1;
for (int i = 1; i < maxLevel; ++i)
if (r < powers[i])
return i-1;
return i-1;
}
template<class T>
T* skipList<T>::skipListSearch(const T& key)
{
if (isEmpty())
return nullptr;
nodePtr prev = nullptr, curr = nullptr;
int lvl = 0;
for (lvl = maxLevel - 1; lvl >= 0 && !root[lvl]; --lvl); //find the highest non-null level;
prev = curr = root[lvl];
while(true)
{
if(key == curr->key)
return &curr->key;
else if (key < curr->key)
{
if (!lvl)
return 0;
else if (curr == root[lvl])
curr = root[--lvl];
else curr = *(prev->next + --lvl);
}
else
{
prev = curr;
if (*(curr->next + lvl) != 0)
curr = *(curr->next + lvl);
else
{
for (lvl--; lvl >=0 && *(curr->next + lvl) == 0; --lvl);
if (lvl >= 0)
curr = *(curr->next + lvl);
else return 0;
}
}
}
}
template<class T>
void skipList<T>::skipListInsert(const T& key)
{
nodePtr curr[maxLevel], prev[maxLevel], newNode;
int lvl, i;
curr[maxLevel-1] = root[maxLevel-1];
prev[maxLevel-1] = 0;
for (lvl = maxLevel - 1; lvl >= 0; --lvl)
{
while (curr[lvl] && curr[lvl]->key < key)
{
prev[lvl] = curr[lvl];
curr[lvl] = *(curr[lvl]->next + lvl);
}
if (curr[lvl] && curr[lvl]->key == key)
return;
if (lvl > 0)
if (!prev[lvl])
{
curr[lvl-1] = root[lvl-1];
prev[lvl-1] = 0;
}
else
{
curr[lvl-1] = *(prev[lvl]->next + lvl-1);
prev[lvl-1] = prev[lvl];
}
}
lvl = chooseLevel();
newNode = new skipListNode<T>;
newNode->next = new nodePtr[sizeof(nodePtr) * (lvl+1)];
newNode->key = key;
for (i = 0; i <= lvl; ++i)
{
*(newNode->next + i) = curr[i];
if (prev[i] == 0)
root[i] = newNode;
else *(prev[i]->next + i) = newNode;
}
}
