Linked List

Campared with vector, linked list has no requirement in terms of the continulity of the physical adress, although all the elements’ arrangement are logicaly linear.


By virtual of pointers, linked list can be implemented as the figure above. Above all we should define the node class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
typedef int Rank;
template <typename T>
struct node
{
	//members 
	T data;
	node *pred;
	node *succ;
	//constructor
	node(){} 
	node(T& e,node<T> *p=NULL,node<T> *s=NULL)
	{
		data=e;
		pred=p;
		succ=s;
	}
	//interface
	node<T>* insertAsPred(T const & e);
	node<T>* insertAsSucc(T const & e);
};

Then we have the list template class:
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
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include "node.h"                  //introduce node class
template <typename T>
class list
{
	private:
		int _size;
		
		node<T> *header;
		
		node<T> *trailer;
		
	
	protected:
		void init();                       //init when list created
		
		int clear();                       //clear all nodes
		
		void copyNodes(node<T>*,int);      //copy n nodes from position p
		
	    void merge(node<T> *p,int n,list<T> & L,node<T>* q,int m);	//merge n nodes from p in this list and m nodes from q in list L
		
		void MergeSort(node<T> *p,int n);
		
		void SelectionSort(node<T> *,int);
		
		void InsertSort(node<T>*,int);
		
		
	public:
	
		//constructor
		list(){init();}                    //default
		
		list(list<T> const &L);            //totally copy list L
		
		list(list<T> const& L,Rank r,int n);//copy n nodes from the rth in list L
		
		list(node<T>* p,int n);             //copy n nodes from node p
		
		//destructor
		~list();                           //delete all nodes including sentinel nodes
		
		//read-only interface
		Rank size() const {return _size;}
		
		bool empty(){return (_size<=0);}     //return true, if list is empty
		
		T& operator [] (Rank r) const;     //overload, support call-by-rank (inefficient)
		
		node<T>* first() const {return header->succ;}//position of the first node
		
		node<T>* last() const {return trailer->pred;}//position of the last node
		
		bool valid(node<T>* p)                //check if valid
		{return p&&(header!=p)&&(trailer!=p);}  //sentinel nodes regarded as NULL
		
		bool disordered() const;           //check if list sorted
		
		node<T>* find(T const & e) const
		{return find(e,_size,trailer);}
		
		node<T>* find(T &e,int n,node<T>* p) const; //search in unsorted list
		
		node<T>* search(T const & e) const
		{return search(e,_size,trailer);}
		
		node<T>* search(T const& e,int n,node<T>* p) const; //search in sorted list
		
		node<T>* selectMax(node<T>* p,int n);
		
		node<T>* selectMax(){return selectMax(header->succ,_size);};
		
		//writable interface
		node<T>* insertAsFirst(T const& e);
		
		node<T>* insertAsLast(T const& e); 
		
		node<T>* insertP (node<T>* p, T const & e);   //insert as the predecessor of node p
		
		node<T>* insertS (node<T>* p, T const & e);   //insert as the successor of node p
		
		T remove (node<T>* p);                        //delete node p and return data of p
		
		void merge(list<T> & L)
		{merge(first(), _size, L, L.first(), L.size());} //merge all the list 
		
		void sort(node<T>* p, int n);                 //sort one section
		
		void sort(){sort(first(), _size);}                    //sort the whole list
		
		int deduplicate();                            //duplication removal in unsorted list
		
		int uniquify();                               //duplication removal in sorted list
		
		void reverse();                               //invert
		
		void InsertionSort ( node<T>* p, int n );
		
		void MergeSort(node<T>* & p, int n);
		//traverse
		void traverse (void (*) (T& ));               //function pointer
		
		template <typename VST>                       //operator
		void traverse(VST &);                         //function object
};

Implement of partial interface

default constructor

1
2
3
4
5
6
7
8
9
10
11
template <typename T>
void list<T>::init()
{
    header = new node<T>;
    trailer = new node<T>;
    header->succ = trailer;
    header->pred = NULL;
    trailer->pred = header;
    trailer->succ = NULL;
    _size = 0;
}

overload operator []

1
2
3
4
5
6
7
template <typename T>
T & list<T>::operator [] (Rank r) const
{
    node<T>* p =first();
    while(0<r--) p=p->succ;
    return p->data;
}

find

1
2
3
4
5
6
7
template <typename T>
node<T>* list<T>::find (T& e, int n, node<T>* p) const
{
    while(0<n--)
        if (e==(p=p->pred)->data) return p;  //search from right to left
    return NULL;
}

insert

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
//node insertion
template <typename T>
node<T>* node<T>::insertAsPred (T const & e)
{
    node<T>* x = new node(e, pred, this);
    pred->succ = x;
    pred = x;
    return x;
}

template <typename T>
node<T>* node<T>::insertAsSucc (T const & e)
{
    node<T>* x = new node(e, this, succ);
    succ->pred = x;
    succ = x;
    return x;
}
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
//insertion in list
template <typename T>
node<T>* list<T>::insertAsFirst (T const & e)
{
    _size++;
    return header->insertAsSucc(e);
}

template <typename T>
node<T>* list<T>::insertAsLast (T const & e)
{
    _size++;
    return trailer->insertAsPred(e);
}

template <typename T>
node<T>* list<T>::insertS (node<T>* p, T const & e)
{
    _size++;
    return p->insertAsSucc(e);
}

template <typename T>
node<T>* list<T>::insertP (node<T>* p, T const & e)
{
    _size++;
    return p->insertAsPred(e);
}

construction based on copy

1
2
3
4
5
6
7
8
9
10
template <typename T>
void list<T>::copyNodes(node<T>* p, int n)
{
    init();
    while(0<n--)
    {
        insertAsLast(p->data);
        p=p->succ;
    }
}
1
2
3
4
5
6
7
8
9
template <typename T>                         //copy n terms from position p
list<T>::list(node<T>* p, int n) { copyNodes(p, n); }

template <typename T>                         //copy the whole list L
list<T>::list(list<T> const & L) { copyNodes(L.first(), L._size); }

template <typename T>                         //copy n terms from the rth node
list<T>::list(list<T> const & L, Rank r, int n)
{ copyNodes(L[r], n); }

removal

1
2
3
4
5
6
7
8
9
10
template <typename T>
T list<T>::remove(node<T>* p)
{
    T e = p->data;            //back up the data assuming that type T can be directly assigned
    p->pred->succ = p->succ;
    p->succ->pred = p->pred;
    delete p;
    _size--;
    return e;
}

destruction

1
2
3
4
5
6
7
8
9
10
11
template <typename T>
list<T>::~list()
{ clear(); delete header; delete trailer; }

template <typename T>
int list<T>::clear()
{
    int oldsize = _size;
    while(0<_size) remove (header->succ);
    return oldsize;
}

deduplication

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
int list<T>::deduplicate()
{
    if(_size<2) return 0;
    int oldsize=_size;
    node<T>* p = header;
    Rank r=0;
    while( trailer != (p=p->succ) )
    {
        node<T>* q = find(p->data, r, p);   //search the same one among r true successors of p
        q ? remove (q) : r++;
    }
    return oldsize-_size;
}                                           //time complexity O(n^2)

traverse

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T>
void list<T>::traverse ( void (*vist) (T&) )                //by aid of function pointer
{
    for(node<T>* p=header->succ; p!= trailer; p = p->succ)
        vist (p->data);
}

template <typename T> template <typename VST>               //element type and operator
void list<T>::traverse (VST& visit)                         //by aid of function object
{
    for(node<T>* p=header->succ; p!= trailer; p = p->succ)
        vist (p->data);
}

Sorted List

Assume that type T can be campared directly or ralative operators have been overloaded.

deduplication

The same nodes in linked list should be arranged one by one logically corresponding to sorted vector. Using this characteristic we can implement the removal algorithm of repetitive nodes. Position pointer p and q respectively point to each 2 adjacent nodes, if they are the same, delete q, otherwise turn to next 2 adjacent ones. Iterate like this over and over again until all nodes are checked.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T>
int list<T>::uniquify()
{
    if(_size<2) return 0;
    int oldsize = _size;
    node<T>* p = header->succ;
    node<T>* q;
    while(trailer != (q=p->succ) )
    {
        if (p->data != q->data) p=q;
        else remove(q);
    }
    return oldsize-size;                    
} //O(n)

1
2
3
4
5
6
7
8
template <typename T>
node<T>* list<T>::search ( T const & e, int n, node<T>* p ) const 
//find the last one no more than e among n true predcessors of p
{
    while(0<=n--)  
        if((p=p->pred)->data <= e) break;
    return p;
}//if failed, return the predcessor of the left border, use valid() to check if succeed

Though list is sorted, divide and conquer strategy doesn’t work in this case becase of dynamic memmory strategy where the physical adress has no relation with logical order.

Collator

InsertionSort

The algorthm can be easily describe as: cut the whole list into 2 parts, the sorted prefix and unsorted suffix; repeatly transfer the first term of suffix to prefix through iteration.
Utilize the search algorthm, and we can locate the maxmum element no more than e, therefore we just need pick out element e and insert as the successor of the position returned.

1
2
3
4
5
6
7
8
9
10
template <typename T>
void list<T>::InsertionSort ( node<T>* p, int n )
{
    for (int r=0; r<n; r++)
    {
        insertS ( search(p->data,r,p), p->data);
        p=p->succ;
        remove(p->pred);
    }
}//O(n^2)

SelectionSort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
template <typename T>
void list<T>::SelectionSort( node<T>* p, int n )
{
    node<T>* head = p->pred;
    node<T>* tail = p;
    for(int i;i<n;i++) tail = tail->succ;
    while ( 1 < n-- )
    {
        node<T>* max = selectMax (head->succ,n);
        insertP ( tail,remove(max) );
        tail = tail->pred;
    }
}

template <typename T>
node<T>* list<T>::selectMax(node<T>* p, int n)
{
    node<T>* max = p;
    for(node<T>* cur=p;1<n;n--)
        if(!lt((cur=cur->succ)->data,max->data))  //comparator
            max = cur;
}//O(n^2)

MergeSort

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 list<T>::merge(node<T> *p,int n,list<T> & L,node<T>* q,int m)
// merge n elements of this list from position p with m ones of list L from q
{
    node<T>* pp=p->pred;
    while(0<m)
        if( (0<n)&&(p->data<=q->data) )
        {
            if (q==(p=p->succ)) break;
            n--;
        }
        else
        {
            insertP(p,L.remove((q=q->succ)->pred));
            m--;
        }
    p=pp->succ;
}

template <typename T>
void list<T>::MergeSort(node<T>* & p, int n)
{
    if(n<2) return;
    int m=n>>1;
    node<T>* q=p;
    for(int i=0;i<m;i++) q=q->succ;
    MergeSort(p,m);MergeSort(q,n-m);
    merge(p, m, *this, q, n-m);
}//O(nlogn)

When dividing subsequence, the mergesort algorthm of vector and list have subtle but essential difference. Vector supports call-by-rank which means it can determine the mid point in , while list only support call-by-position and has to pay for it. Fortunately when merging the subsequences, they all need , therefore asymptotically the 2 time complexities are still equal.

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

刘越, <br>中国矿业大学CS在读。<br><br>喜欢记录，爱好破事水