Lists
This lesson describes lists with a cursor and provides two implementations for them. Lists enable storing, quering and traversing a sequence of elements in a sequential way. Lists with a cursor can only be accessed in one position at any time, so they are less powerfull than lists with iterators (but are also simpler to implement).
A list with a cursor is a sequence of elements that has a (unique) cursor between the elements, as well as before the frist and after the last element. We denote such a list with a cursor using the [40,12,35;23,39] notation, which means that the list corresponds to the sequence [40, 12, 35, 23, 39] and that its cursor is placed between its third and fourth elements (35 and 23). Observe the use of the commas and the semicolon.
The list can be traversed by moving the cursor sequentially to the left or to the right, as well as moving it directly before the start or past the end of the sequence. The following table illustrates the possible movements on the list [40,12,35;23,39]:
| movement | result |
|---|---|
move_to_start |
[;40,12,35,23,39] |
move_to_end |
[40,12,35,23,39;] |
move_to_left |
[40,12;35,23,39] |
move_to_right |
[40,12,35,23;39] |
The get operation returns the elements after the cursor. Elements are
inserted before the cursor and are removed after the cursor. In order to
remember it, think about a text box where keys insert elements before the
cursor and where the delete key erases the character after the cursor:
Implementation with two stacks
In this implementation, a list is represented by two stacks, the left stack and the right stack, which face each other. The elements before the cursor are in the left stack and the elements after the cursor are in the right stack.
For instace, the list [40,12,35;23,39] is represented by the [40,12,35[ left stack and the ]23,39] stack. Moving the cursor involves moving the top elements between the stacks. Accessing elements around the cursors involves accessing the top elements of the stacks.
#include <stack>
#include <cassert>
using namespace std;
template <typename T>
class List {
/** Left and right stacks. */
stack<T> left, right;
public:
/** Creates an empty list. */
List ()
{ }
/** Returns the number of elements in the list. */
int size () const {
return left.size() + right.size();
}
/** Tells whether the list is empty. */
bool empty () const {
return size() == 0;
}
/** Tells whether the cursor is at the beginning of the list. */
bool is_at_start () const {
return left.empty();
}
/** Tells whether the cursor is at the end of the list. */
bool is_at_end () const {
return right.empty();
}
/** Moves the cursor one position to the left.
Precondition: the cursor is not at the start of the list.
*/
void move_left () {
transfer(left, right);
}
/** Moves the cursor one position to the right.
Precondition: the cursor is not at the end of the list.
*/
void move_right () {
transfer(right, left);
}
/** Moves the cursor to the beginning of the list. */
void move_to_start () {
while (not is_at_start()) move_left();
}
/** Moves the cursor to the end of the list. */
void move_to_end () {
while (not is_at_end()) move_right();
}
/** Inserts an element x before the cursor. */
void insert (const T& x) {
left.push(x);
}
/** Erases the element after the cursor.
Precondition: the cursor is not at the end of the list.
*/
void erase () {
assert(not is_at_end());
right.pop();
}
/** Returns the element after the cursor.
Precondition: the cursor is not at the end of the list.
*/
T get () const {
assert(not is_at_end());
return right.top();
}
private:
/** Transfers the top element of the source stack to the destionation stack.
Precondition: the source stack is not empty.
*/
static void transfer (stack<T>& src, stack<T>& dst) {
assert(not src.empty());
dst.push(src.top());
src.pop();
}
};
The cost of all operations is constant, except for move_to_start and
move_to_end, which are linear in the worst case.
Implementation with doubly linked nodes
In this implementation a list is represented with a circular doubly linked list of nodes with a ghost element (noted 👻). The ghost element is not necessary but provides an easier implementation.
Each list has two pointers to the nodes of its circular doubly linked list of nodes:
ghostpoints to the ghost node.cursorpoints to the element after the cursor.
FALTA ACTAULITZAR DIBUIXOS PER FERLOS CIRCULARS
For instace, list [40,12,35;23,39] would be represented like this:
beg cur end
↓ ↓ ↓
├─ 40 ⟷ 12 ⟷ 35 ⟷ 23 ⟷ 39 ⟷ 👻 ─┤
Likewise, list [40,12,35,23,39;] would be represented like this:
cur
beg end
↓ ↓
├─ 40 ⟷ 12 ⟷ 35 ⟷ 23 ⟷ 39 ⟷ 👻 ─┤
To be clear, the empty list [;] is as shown:
beg
end
cur
↓
├─ 👻 ─┤
The implementation follows:
#include <cassert>
using namespace std;
template <typename T>
class List {
/** Node with an element, and pointers to the previous and next nodes. */
struct Node {
Node* prev;
T elem;
Node* next;
};
/** Ghost node for the list. */
Node* ghost;
/** Pointer to the node after the cursor. */
Node* cursor;
/** Number of elements in the list. */
int n;
public:
/** Creates an empty list. */
List ()
: ghost(new Node),
cursor(ghost),
n(0)
{
ghost->prev = ghost->next = ghost;
}
/** Copy constructor. */
List (const List& L) {
copy(L);
}
/** Destructor. */
~List () {
free();
}
/** Assignment. */
List& operator= (const List& L) {
if (&L != this) {
free();
copy(L);
}
return *this;
}
/** Returns the number of elements in the list. */
int size () const {
return n;
}
/** Tells whether the list is empty. */
bool empty () const {
return size() == 0;
}
/** Tells whether the cursor is at the front of the list. */
bool is_at_front () const {
return cursor == ghost->next;
}
/** Tells whether the cursor is at the end of the list. */
bool is_at_end () const {
return cursor == ghost;
}
/** Moves the cursor one position to the left.
Precondition: the cursor is not at the front of the list.
*/
void move_left () {
assert(not is_at_front());
cursor = cursor->prev;
}
/** Moves the cursor one position to the right.
Precondition: the cursor is not at the end of the list.
*/
void move_right () {
assert(not is_at_end());
cursor = cursor->next;
}
/** Moves the cursor to the front of the list. */
void move_to_front () {
cursor = ghost->next;
}
/** Moves the cursor to the end of the list. */
void move_to_end () {
cursor = ghost;
}
/** Inserts an element x before the cursor. */
void insert (const T& x) {
cursor->prev = cursor->prev->next = new Node {cursor->prev, x, cursor};
++n;
}
/** Erases the element after the cursor.
Precondition: the cursor is not at the end of the list.
*/
void erase () {
assert(not is_at_end());
Node *p = cursor;
p->next->prev = p->prev;
cursor = p->prev-next = p->next;
delete p;
--n;
}
/** Returns the element after the cursor.
Precondition: the cursor is not at the end of the list.
*/
T get () const {
assert(not is_at_end());
return cursor->elem;
}
private:
/** Copies the list L. */
void copy (const List& L) {
n = L.n;
Node* q = cursor = ghost = new Node;
Node* p = L.ghost->next;
while (p != L.ghost) {
q = q->next = new Node {q, p->elem};
if (p == L.cursor) cursor = q;
p = p->next;
}
q->next = ghost;
ghost->prev = q;
}
/** Frees the linked list of nodes in the list. */
void free () {
Node* p = ghost->next;
while (p != ghost) {
Node* old = p;
p = p->next;
delete old;
}
delete p;
}
};
The cost of all operations is constant, except for the copy operations, which are linear, of course.
Lliçons.jutge.org
Jordi Cortadella, Jordi Petit, Salvador Roura
Universitat Politècnica de Catalunya, 2023
Prohibit copiar. Tots els drets reservats.
No copy allowed. All rights reserved.