# 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”

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


### 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

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$

 1 2 3 4 5 6 7  template 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 void Vector::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 void Vector::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 void Vector::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 void Vector::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)$

1. Logic is Contiguous, and physical is Contiguous
2. Random access any element

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

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

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

Only traversed in one direction

Pointer in the last node points back to the first node

Allows traversals both forwards and backwards

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

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

empty list

$head\rightarrow null$

$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 class ListNode; template using ListNodePosition = ListNode *; template class ListNode { public: T data{}; ListNodePosition successor{}; } //List without headNode using Rank = int; template class List { protected: ListNodePosition head; Rank _size; } 

code

 1 2 3 4 5 6 7  template T &List::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 ListNodePosition ListNode::insertAsSuccessor(const T &Val) { auto temp = new ListNode{Val, successor}; successor = temp; return temp; } //node template ListNodePosition ListNode::insertAsSuccessor(ListNodePosition listNodePosition) { listNodePosition->successor = successor; successor = listNodePosition; return listNodePosition; } 

delete

  1 2 3 4 5 6 7 8 9 10 11  //by the rank template void List::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--; } 

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

$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$

$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 class ListCircle { protected: ListNodePosition head; Rank _size; public: ListCircle(); ListCircle(std::initializer_list args); [[nodiscard]] Rank size() const; void clear(); Rank DeleteNode(Rank index); void traverse(void(*visit)(T &)); ~ListCircle(); }; template ListCircle::ListCircle() :head{new ListNode{T{}, nullptr}}, _size{0} { head->successor = head; } template ListCircle::ListCircle(std::initializer_list args) :ListCircle() { _size = static_cast(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 Rank ListCircle::size() const { return _size; } template void ListCircle::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 ListCircle::~ListCircle() { clear(); delete head; } template Rank ListCircle::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 void ListCircle::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); } } 

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 T List::remove ( ListNodePosi 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; } 

structure

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

empty

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

Summary

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

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.

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.

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

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.

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.

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