blob: e430108b8591f1cc8094e9350a93edcd6f861660 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
|
/**@file
* Describes the LinkedList implementation of the List ADT.
*@author Mike Buland
*/
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <stdio.h>
#include "list.h"
/** A linked-item implementation of the List ADT. Since the data is linked
* sequentially this is a great choice for lists that will grow and shrink
* a lot, but don't require as much random access. This implementation
* includes optomizations that make iterating through data, and appending
* items to the list take O(1) time.
*@author Mike Buland
*/
class LinkedList : public List
{
public:
/**
* Construct a blank LinkedList.
*/
LinkedList();
/**
* Delete all list data, but do not delete any of the contained elements.
*/
virtual ~LinkedList();
void *getAt( int nIndex );
void append( void *pData );
void insertBefore( void *pData, int nPos = 0 );
int getSize( );
bool isEmpty( );
void deleteAt( int nIndex );
void empty();
void setSize( int nNewSize );
void setAt( int nIndex, void *pData );
private:
/**
* A link in the linked list.
*/
class Link
{
public:
/**
* Construct an empty link.
*/
Link()
{
pData = NULL;
pNext = NULL;
}
/**
* Construct a link filled in with useful data.
*@param newData The data this link should hold.
*@param newNext The next link that this link should point to.
*/
Link( void *newData = NULL, Link * newNext = NULL )
{
pData = newData;
pNext = newNext;
}
void *pData; /**< A pointer to the contained data. */
Link *pNext; /**< A pointer to the next link in the chain */
};
/**
* Finds a pointer to the link at index index. This is the core function
* called for all seek operations, and has been optimized as heavily as
* possible.
*@param index The zero-based index of the desired element.
*@returns A pointer to the requested Link, or NULL if it isn't found.
*/
Link *getPtrTo( int index );
Link *pBase; /**< The first link in the list. */
Link *pTop; /**< The Last link in the list. */
Link *pLast; /**< The previously requested link. */
int nSize; /**< The number of contained links. */
int nLast; /**< The index of the previously requested link. */
};
#endif
|
