Data Structure

List

Definition

A list is a finite sequence of N elements

$write\ as\newline$ $L = (a_1, a_2, a_3，…a_n)\newline$

$The\ size\ of\ this\ list\ is\ n\newline$

$n=0 \rightarrow empty\ list\newline$

element

1. The first element(No predecessor),called “head”
2. The ith element(has only one predecessor and only one successor)
3. The last element(No successor),called “tail”

ADT

ADT List {

Data object：D = {ai | ai∈Elements, (i=1,2,…,n, n≥0)}

Data relationship ： R1 = { ＜ ai-1,ai ＞ |ai-1,ai ∈ D,
(i=2,3,…,n) }

Operations：
• InitList(&L);
• DestroyList(&L);
• ListInsert(&L,i,e); 
• ListDelete(&L,i,&e);
……and so on

} ADT List

Operation

{

InitList(&L):Create a empty list
DestroyList(&L):Delete a list(L has been initialized)
ClearList(&L):make L be an empty list(L has been initialized)

ListLength(L):return the size of elements in the list(L has been initialized)
ListEmpty(L):return if the list is an empty list(L has been initialized)

GetElem(L, i, &e): 
make e equaled to the ith element in the list(L has been initialized and 1 <= i <= ListLength(L))
LocateElem(L, e, compare()): 
return the rank that the rank of the element is the first element which compare(element[rank], e) is true(L has been initialized),
if no element satisfy it, return 0

PriorElem(L, cur_e, &pre_e): 
make the pre_e equal the predecessor of the element which is the first which equal to cur_e, or return FAIL(L has been initialized)
NextElem(L, cur_e, &next_e):
make the next_e equal the successor of the element which is the first which equal to cur_e, or return FAIL(L has been initialized)

ListInsert(&L, i, e): 
insert the element in the ith rank of the list(L has been initialized)
ListDelete(&L, i, &e):
delete the ith element in the list(L has been initialized and not be empty)

ListTraverse(&L, visit()):
    for (begin, end)
        visit(list[rank]_data)
(L has been initialized)

}

Example: make $ListA \bigcup ListB$

The code

1
2
3
4
5
6
7
8
9

void union(List &a, List &b) {
    La_len = ListLength(a);
    Lb_len = ListLength(b);
    for (int i = 1; i <= Lb_len; i++) {
        GetElem(Lb_len, i, e);
        if (!LocateElem(a, e, equal))
            ListInsert(a, ++La_len, e);
    }
}

Merge List

 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

void MergeList(List La, List Lb, List &Lc){
        InitList(Lc); 
        int i = j = 1;
        int k = 0;
        int La_len = ListLength(La);
        int Lb_len = ListLength(Lb);
        While ((i <= La_len) && (j <= Lb_len)){ //La和Lb均非空
            GetElem(La,i,ai); GetElem(Lb,j,bj);
            if (ai <= bj) {
                ListInsert(Lc, ++k, ai); 
                ++i;
            }
            else { 
                ListInsert(Lc, ++k, bj); 
                ++j;
            }
        }
        while (i <= La_len) {
            GetElem(La,i++,ai); 
            ListInsert(Lc, ++k, ai);
        }
        while (j <= Lb_len) {
            GetElem(Lb,j++,bj); 
            ListInsert(Lc,++k, bj);
        }   
}// MergeList

Implementation of Lists

Array implementation of lists

Using consecutive storage units to store elements of a list,the elements are stored in the logic order

k—- the memory space size for one element

The address of the (i+1)th element->Loc(ai+1) = Loc(ai) + k

Loc(a1)—-base address of the list

The address of the ith element:->Loc(ai) = Loc(a1) + (i-1)*k

$logic\ Element: [a_0, a_1, …, a_n]\newline$ $Physical\ Element:{[locate(a_0)]\ [locate(a_1)]\ …\ [locate(a_n)]}\newline$

$!!!\ Storage\ structure: random\ storage$

about data

1
2
3
4
5
6
7

template<typename T>
class Vector {
protected:
    T *_data;
    Rank _size{};
    Rank _capacity{};
}

supplement expend and shrink

 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

template<typename T>
void Vector<T>::expand() {
    if (_capacity >= AUTO_INITIALIZER && _size < _capacity >> 1)
        return;
    if (_capacity < AUTO_INITIALIZER)
        _capacity = AUTO_INITIALIZER;
    if (_size >= _capacity >> 1)
        _capacity <<= 1;
    T *OldData = _data;
    _data = new T[_capacity]{};
    for (Rank i = 0; i < _size; i++)
        _data[i] = OldData[i];
    delete[]OldData;
}


template<typename T>
void Vector<T>::shrink() {
    if (_capacity < AUTO_INITIALIZER || _size >= _capacity >> 1)
        return;
    else {
        _capacity >>= 1;
        T *OldData = _data;
        _data = new T[_capacity]{};
        for (Rank i = 0; i < _size; i++)
            _data[i] = OldData[i];
        delete[]OldData;
    }
}

T(n) = O(n)

insert

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

template<typename T>
void Vector<T>::insert(const T &Val, Rank size) {
    if (size > _size) throw std::out_of_range{"The array is out of range!"};
    else {
        expand();
        for (Rank i = _size; i > size; i--)
            _data[i] = _data[i - 1]; //Prevents data from being overwritten
        _data[size] = Val;
        _size++;
    }
}

!!!The number of elements moved depends on the length of the order table and the location of the inserted element.

!!!Average:

$T(n) = \frac{\sum_{i=0}^n i}{n + 1} = \frac{\frac{n(n + 1)}{2}}{n + 1} = \frac {n}{2} = O(n)$

delete

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

template<typename T>
void Vector<T>::remove(Rank size) {
    if (size >= _size) throw std::out_of_range{"out of range"};
    else {
        for (Rank i = size; i < _size - 1; i++)
            _data[i] = _data[i + 1];
        _size--;
        shrink();
    }
}

!!!The number of elements moved depends on the length of the order table and the location of the deleted element

!!!Average:

$T(n) = \frac{\sum_{i = 0}^{n - 1} i}{n} = \frac{\frac{n(n - 1)}{2}}{n} = \frac{n - 1}{2} = O(n)$

Advantage

1. Logic is Contiguous, and physical is Contiguous
2. Random access any element
3. The address can be calculated by base address

Disadvantage

1. Insertion and deletion must move lot of elements
2. Must assign memory with maximum-size
3. It is not easy to extend array size

Linked list implement of lists

1. Connected by pointer links
2. Accessed via a pointer to the first node of the list
3. Subsequent nodes are accessed via the link-pointer member of the current node
4. Link pointer in the last node is set to null to mark the list’s end

Use a linked list instead of an array when

1. You have an unpredictable number of data elements
2. Your list needs to be sorted quickly

Types of linked list

1. Singly linked list

   Only traversed in one direction

2. Circular, singly linked list

   Pointer in the last node points back to the first node

3. Doubly linked list

   Allows traversals both forwards and backwards

4. Circular, doubly linked list

   Forward pointer of the last node points to the first node and backward pointer of the first node points to the last node

Singly Linked list

without head node

$head(pointer) \rightarrow [a_1] [pointer]\rightarrow [a_2] [pointer]\rightarrow ……\rightarrow [a_n] [pointer]\rightarrow null$

empty list

$head\rightarrow null$

with head node

$head(pointer)\rightarrow [head] [pointer]\rightarrow [a_1] [pointer]\rightarrow [a_2] [pointer]\rightarrow ……\rightarrow[a_n] [pointer]\rightarrow null$

empty list

$head\rightarrow [head] [pointer]\rightarrow null$

code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

//ListNode
template<typename T>
class ListNode;

template<typename T>
using ListNodePosition = ListNode<T> *;

template<typename T>
class ListNode {
public:
    T data{};
    ListNodePosition<T> successor{};
}


//List without headNode
using Rank = int;

template<typename T>
class List {
protected:
    ListNodePosition<T> head;
    Rank _size;
}

address data

code

1
2
3
4
5
6
7

template<typename T>
T &List<T>::operator[](Rank index) {
    auto temp = head->successor;
    for (Rank i = 0; i < index; i++)
        temp = temp->successor;
    return temp->data;
}

insert node

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

//data
template<typename T>
ListNodePosition<T> ListNode<T>::insertAsSuccessor(const T &Val) {
    auto temp = new ListNode<T>{Val, successor};
    successor = temp;
    return temp;
}

//node
template<typename T>
ListNodePosition<T> ListNode<T>::insertAsSuccessor(ListNodePosition<T> listNodePosition) {
    listNodePosition->successor = successor;
    successor = listNodePosition;
    return listNodePosition;
}

delete

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

//by the rank
template<typename T>
void List<T>::Delete(Rank index) {
    auto temp = head;
    for(Rank i = 0; i < index; i++)
        temp = temp->successor;
    auto record = temp->successor;
    temp->successor = record->successor;
    delete record;
    _size--;
}

Circular, singly linked list

A Feature of the circulated linked lists—the next pointer of the last node points to the head, so the linked list becomes a circle

Any node can be found from any given node

structure

without head node

$head(pointer) \rightarrow [a_1] [pointer]\rightarrow [a_2] [pointer]\rightarrow ……\rightarrow [a_n] [pointer]\rightarrow head, tail \rightarrow [a_n]$

empty list

$head\rightarrow head, tail\rightarrow head$

with head node

$head(pointer)\rightarrow [head] [pointer]\rightarrow [a_1] [pointer]\rightarrow [a_2] [pointer]\rightarrow ……\rightarrow[a_n] [pointer]\rightarrow [a_0]$

empty list

$head\rightarrow [head] [pointer]\rightarrow [head]$

code

 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
88

using Rank = int;

template<typename T>
class ListCircle {
protected:
    ListNodePosition<T> head;
    Rank _size;
public:
    ListCircle();

    ListCircle(std::initializer_list<T> args);

    [[nodiscard]] Rank size() const;

    void clear();

    Rank DeleteNode(Rank index);

    void traverse(void(*visit)(T &));

    ~ListCircle();
};

template<typename T>
ListCircle<T>::ListCircle() :head{new ListNode<T>{T{}, nullptr}}, _size{0} {
    head->successor = head;
}

template<typename T>
ListCircle<T>::ListCircle(std::initializer_list<T> args) :ListCircle() {
    _size = static_cast<Rank>(args.size());
    auto iter = head;
    auto begin = args.begin();
    for (Rank i = 0; i < _size; i++) {
        iter->insertAsSuccessor(*(begin + i));
        iter = iter->successor;
    }
    iter->successor = head;
}

template<typename T>
Rank ListCircle<T>::size() const {
    return _size;
}

template<typename T>
void ListCircle<T>::clear() {
    if (_size == 0)
        return;
    else {
        auto temp = head->successor;
        for (Rank i = 0; i < _size; i++) {
            auto record = temp;
            temp = temp->successor;
            delete record;
        }
        _size = 0;
    }
}

template<typename T>
ListCircle<T>::~ListCircle() {
    clear();
    delete head;
}

template<typename T>
Rank ListCircle<T>::DeleteNode(Rank index) {
    auto temp = head;
    for (Rank i = 0; i < index; i++)
        temp = temp->successor;
    auto record = temp->successor;
    temp->successor = record->successor;
    delete record;
    _size--;
    return index;
}

template<typename T>
void ListCircle<T>::traverse(void (*visit)(T &)) {
    if (_size == 0)
        std::cout << "Empty List" << std::endl;
    else {
        auto temp = head->successor;
        for (Rank i = 0; i < _size; i++, temp = temp->successor)
            visit(temp->data);
    }
}

Doubly linked list

The feature of double linked lists —- There are two pointer fields in one node, one points to the predecessor, another to the successor

Any node in the list can be found by tracing back and forth from any given node.

structure

$[a_{i-1}]^\rightarrow_\leftarrow[prior] [data] [next]^\rightarrow_\leftarrow[a_{i + 1}]$

no empty list

$L\rightarrow[head]\rightarrow[a_1]^\rightarrow_\leftarrow[a_2]^\rightarrow_\leftarrow……^\rightarrow_\leftarrow[a_n]\rightarrow null\newline$ $head.prior\rightarrow[a_n]\newline$

empty list

$L\rightarrow prior = L\rightarrow next = null$

delete

1
2
3
4
5
6
7
8

template <typename T> T List<T>::remove ( ListNodePosi<T> p ) {
   T e = p->data;
   p->pred->succ = p->succ; 
   p->succ->pred = p->pred;
   delete p; 
   _size--;
   return e;
}

insert

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

bool ListInsert_DuL(DuLinklist &L, int i, ElemType e) {
    DuLinklist s,p;
    if (!(p=GetElemP_DuL(L,i))) 
    return ERROR;
    if(!(s = (DuLinklist)malloc(sizeof(DuLNode)))) 
    return ERROR;
    s->data = e; 
    s->prior = p->prior; s->next = p;
    p-> prior ->next = s; p->prior = s;
    return OK;
} 

Circular, doubly linked list

structure

without head

$head\rightarrow prior = [a_n]\ a_n\rightarrow next = head$

empty

$head\rightarrow prior = head\rightarrow next = head$

Summary

Advantage

1. store items “sequentially” without restrictions on location
2. insert new item without shifting
3. delete existing item without shifting
4. size can expand/contract throughout use

Disadvantage

1. overhead of links: used only internally, pure overhead
2. no longer have direct access to each element of the list. O(1) access becomes O(n) access since we must go through first element, and then second, and then third, etc.

Select ArrayedList or LinkedList?

Array-Based List:

1. Insertion and deletion are O(n).
2. Direct access are O(1).
3. Array must be allocated in advance.
4. No overhead if all array positions are full.

Linked List:

1. Insertion and deletion are O(1).
2. Direct access are O(n).
3. Space grows with number of elements.
4. Every element requires overhead.

Contiguous storage is generally preferable:

1. when the entries are individually very small;
2. when the size of the list is known when the program is written;
3. when few insertions or deletions need to be made except at the end of the list;
4. when random access is important.

Linked storage proves superior

1. when the entries are large;
2. when the size of the list is not known in advance
3. when flexibility is needed in inserting, deleting, and rearranging the entries.

Other:Cursor Implementation of Linked List

implementation in a consecutive storage, and the next is not a pointer but a Rank to search next node

1. You still need to allocate a large space beforehand;
2. But in the linear table insert and delete operations do not need to move elements, only need to modify the cursor (pointer), so it still has the main advantages of chain storage structure;
3. A linked list described by an array is called a static linked list.

Application of Linked list:

Example: Polynomials

$P(x) = a_0 + a_1x + a_2x^2 + … + a_nx^n$

Array-based implementation:Disadvantage: for sparse polynomials ->waste memory!

Linked list implementation can solve the problem

About Homework

you can use Singly linked list like a stack (push and pop)