Chapter 3
Linear List
3.1 Preface
1,data object---
a set of instances or values
for example,
Boolean={false,true}
Digit={0,1,2,3,4,5,6,7,8,9}
Letter={A,B,……Z,a,b,……z}
NaturalNumber={0,1,2,……}
Integer = {0,+1,-1,+2,-2,+3,-3,…}
String={a,b,……,aa,ab,ac,……}
3.1 Preface
２,data structure
is a data object together with the relationships
among the instances and among the individual
elements that compose an instance
? Data_Structure={D,R}
? D---data object，
? R ---a set of relationships of all the data members in
D.
3.2 Linear List
L = (e1,e2,e3,…,en)
list size is n
if n=0,empty list
if n>0,
e1 is the first’th (or front) element
en is the last element
ei immediately precedes ei+1
3.2 Linear List
Example:
Students =(Jack,Jill,Abe,Henry,Mary,…,
Judy)
Exams =(exam1,exam2,exam3)
Days of Week = (S,M,T,W,Th,F,Sa)
Months = (Jan,Feb,Mar,Apr,…,Nov,Dec)
3.2 Linear List
Operations:
Create a linear list
determine whether the list is empty
determine the length of the list
find the kth of the element
search for a given element
delete the kth element
insert a new element just after the kth
3.2 Linear List
ADT specification of a linear list
AbstractDateType LinearList
{ instances
ordered finite collections of zero or more elements
operations
Create(); Destroy();
IsEmpty(); Length();
Find(k,x); Search(x);
Delete(k,x); Insert(k,x);
Output(out);
}
3.3 Formula-based Representation
1,Use an array to represent the instance of
an object
(e1,e2,………e n) length=n
each position of the array is called a cell or a
node
mapping formula:location(i)=i-1
e1 e2 e3 en
Element 0 1 2 n-1 maxsize-1
3.3 Formula-based Representation
2,Class definition,program 3.1
template <class T>
class LinearList{
public:
LinearList(int MaxListSize =10);
~ LinearList(){ delete [] element;};
bool IsEmpty() const {return length= =0;}
int Length() const (return length);
bool Find(int k,T&x) const;
int Search(const T&x) const;
LinearList <T>& Delete(int k,T&x);
LinearList <T>& Insert(int k,const T&x);
void Output(ostream& out) const;
private:
int length; int MaxSize; T* element;
}
3.3 Formula-based Representation
3,Operations:
1) Constructor,
template <class T>
LinearList<T>::LinearList(int MaxListSize)
{
MaxSize=MaxListSize;
element=new T[MaxSize];
length=0;
}
3.3 Formula-based Representation
2) bool Find(int k,T&x) O(1)
the k?th element in the list in x
L = (a,b,c,d,e)
find(1,x) = true,x=a
find(2,x) = true,x=b
find(4,x) = true,x=d
find(0,x) = error
find(9,x) = error
3.3 Formula-base Representation
program 3.3
template <class T>
bool LinearList<T>:,Find(int k,T &x) const
{ if (k<1|| k>length) return false;
x= element[k-1];
return true;
}
3.3 Formula-based Representation
3) search(const T&x) O(length)
return the index of x if found,otherwise return 0
L = (a,b,d,b,e)
search(d) = 3
search(a) = 1
search(z) = 0
3.3 Formula-based Representation
program 3.3
template <class T>
int LinearList <T>::Search(const T & x) const
{ for ( int i=0 ; i < length; i++)
if (element[i]==x) return ++i;
return 0;
}
3.3 Formula-based Representation
4) delete (int k,T&x)
delete the k’th element and return it in x
L = (a,b,c,d,e)
delete(2,x) =>
L=(a,c,d,e),x=b,
and index of c,d,e decrease by 1
delete(0,x) => error
delete(20,x) => error
3.3 Formula-based Representation
Program 3.4
template <class T>
LinearList <T>& LinearList <T>::Delete( int k,T & x)
{ if (Find(k,x))
{ for ( int i=k; i<length; i++)
element[i-1]=element[i];
length--;
return *this;
}
else throw OutOfBounds()
}
3.3 Formula-based Representation
5) insert (int k,const T&x)
insert x after the k?th element
L = (a,b,c,d,e,f,g)
insert(0,h) => L = (h,a,b,c,d,e,f,g)
index of a,b,c,d,e,f,and g increase by 1
insert(10,h) => error
insert(-6,h) => error
3.3 Formula-base Representation
Program 3.5:
template <class T>
LinearList <T> &LinearList <T>::insert(int k,const T &x)
{ if (k<0 || k> length ) throw OutOfBounds();
if ( length = = MaxSize) throw NoMem();
for ( int i= length-1; i>=k; i--)
element[i+1] = element[i] ;
element[k] = x ;
length++;
return *this;
}
3.3 Formula-based Representation
4,Let?s see an example using the class linear
list(program 3.7)
3.4 Linked Representation
1) Each node of a data object keeps a link or
a pointer about the location of other relevant
nodes
L=(e1,e2,………e n)
first
linked field …..,null
data field e1 e2 e3 en
3.4 Linked Representation
? The figure above is called a single linked
list,and the structure is also called a chain
? A chain is a linked list in which each node
represents one element.
? There is a link or pointer from one element
to the next.
? The last node has a null pointer.
3.4 Linked Representation
2,Classes Chain and ChainNode definition
program 3.8
template <class T> class ChainNode
{ friend Chain <T> ;
private:
T data;
chainNode<T> *link;
}
3.4 Linked Representation
template <class T> class Chain
{ public:
Chain( ){first=0;}
~Chain( );
bool IsEmpty( )const{ return first= =0;}
int Length( ) const;
bool Find(int k,T & x)const;
int Search(const T & x) const;
Chain<T>&Delete(int k,T& x);
Chain<T>&Insert(int k,const T& x);
void Output(ostream& out)const;
private,ChainNode<T> *first;
}
3.4 Linked Representation
3.operations
1)delete all the nodes in a chain
program 3.9
2)determine the length of a chain
program 3.10
3)find the kth element of a chain
program 3.11
3.4 Linked Representation
4)search for a chain
program 3.12
5)output a chain
program 3.13
3.4 Linked Representation
6) Deletion a element of a chain
a b c d e
null
first
first = first->link;
3.4 Linked Representation
first get to node just before node to be removed
before= first ->link;
a b d e
null
first
cc
before
3.4 Linked Representation
now change pointer in before
before ->link = before ->link ->link;
before
a b c d e
null
first
3.4 Linked Representation
Operation delete—program 3.14
template<class T>Chain<T>&Chain<T>::Delete(int k,T& x)
{ if( k<1|| !first)throw OutOfBounds( );
ChainNode<T> *p=first;
if ( k= = 1) first=first->link;
else
{ ChainNode<T> *q=first;
for (int index=1;index < k-1 && q ; index++)
q=q->link;
if (!q || !q->link) throw OutOfBounds( );
p = q->link; q->link = p->link;
}
x = p->data; delete p; return *this;
}
3.4 Linked Representation
a b c d e
nul
l
first
f
newNode
Step 1,get a node,set its data and link fields
ChainNode newNode =
new ChainNode(?f?,first);
7) insert operation ----insert(0,?f?)
3.4 Linked Representation
Step 2,update first
first = newNode;
a b c d e
null
first
f
newNode
3.4 Linked Representation
newNode->link=first;
first = newNode;
a b c d e
null
first
f
newNode
insert(3,?f?)
1,first find node whose index is 3
a b c d e
null
first
f
newNode
before
2,next create a node and set its data and link fields
ChainNode newNode = new ChainNode(?f?,before ->link);
3.finally link before to newNode
before->link = newNode;
Two-Step insert(3,?f?)
before = first ->link ->link;
newNode ->link = before ->link;
before ->link = newNode;
a b c d e
null
first
f
newNode
before
3.4 Linked Representation
Operation insert—program 3.15
template<class T>Chain<T>&Chain<T>::insert(int k,const
T& x)
{ if (k<0) throw OutOfBounds( );
ChainNode<T>*p = first;
for(int index = 1 ; index < k && p; index++)
p = p->link;
if (k>0 && !p) throw OutOfBounds( );
ChainNode<T>*y=new ChainNode<T>;
y->data = x;
if ( k) { y->link = p->link; p->link = y; }
else { y->link = first; first = y; }
return * this;
}
3.4 Linked Representation
4.Extensions to class chain
include some additional functions such as:
1)Erase—delete all nodes in a chain
2)Zero—set the first pointer to 0,but don?t
delete any node
3)Append—add an element to the end of a
chain.(to keep track of the last node in the chain,
we use a new private member ChainNode* last.)
3.5 simply linked Circular List
figure
a b c d e
first
3.5 Simply Linked Circular List
With Head Node
a b c d e
first
headNode
first
headNode
3.5 simply linked Circular List
For example:
Josephus Problem
n=8
m=3
3,6,1,5,2,8,4
7
1
2
3
4
5
6
7
8
3.5 simply linked Circular List
#include<iostream.h>
#include”CircList.h”
template<class T> void CircList<T>::
Josephus(int n,int m)
{ Firster( );
for (int i=0 ; i<n-1 ; i++)
{ for ( int j=0 ; j<m-1 ; j++) Next( );
cout<<“delete person”<<getdata( )<<endl;
remove( );
}
}
3.5 simply linked Circular List
void main( )
{ CircList <int> clist;
int n,m;
cout<<“Enter the Number of contestants?”;
cin>>n>>m;
for ( int i=1; i<=n; i++) clist.insert(i);
clist.Josephus(n,m);
}
3.6 Doubly Linked List
figure
a b c d e
null
firstNode
null
lastNode
3.6 Doubly Linked List
1,Class definition for doubly linked
list( program 3-21)
template<class T> class DoubleNode
{ friend DoubleNode<T>;
private:
T data;
DoubleNode<T>*left,*right;
}
template<class T> class Doubl
{ public:
Double( ){LeftEnd = RightEnd = 0;}
~Double( );
int Length( ) const;
bool Find(int k,T& x)const;
int Search(const T& x) const;
Double<T>&Delete(int k,T & x);
Double<T>& Insert( int k,const T & x);
void Output(ostream & out) const;
private:
DoubleNode<T>*LeftEnd,*RightEnd;
}
3.6 Doubly Linked List
2,Operations,Insert,Delete
3.6 Doubly Linked List
insert(0,?f?)
a b c d e
null
firstNode
null
lastNode
null
newNode firstNode->llink=newNode;
newNode->llink=null; newNode->rlink=firstNode;
firstNode=newNode
3.6 Doubly Linked List
Insert(2,?f?)
a b c d e
null
firstNode
null
lastNode
beforeNode
newNode
newNode->llink=beforeNode; newNode->rlink=beforeNode->rlink;
beforeNode->rlink->llink=newNode; beforeNode->rlink=newNode;
3.6 Doubly Linked List
Delete(1)
a b c d e
null
firstNode
null
lastNode
P=firstNode; firstNode=p->rlink; firstNode->llink=null;
p
null
3.6 Doubly Linked List
Delete(3)
a b c d e
null
firstNode
null
lastNode
p
P->llink->rlink=p->rlink;
P->rlink->llink=p->llink;
Double Linked Circular List
figure
a b c d e
firstNode
Doubly Linked Circular List
With Header Node
figure
a b c e
headerNode
d
Empty Doubly Linked Circular
List With Header Node
headerNode
3.7 simulating pointer
A:
Linear List
3.1 Preface
1,data object---
a set of instances or values
for example,
Boolean={false,true}
Digit={0,1,2,3,4,5,6,7,8,9}
Letter={A,B,……Z,a,b,……z}
NaturalNumber={0,1,2,……}
Integer = {0,+1,-1,+2,-2,+3,-3,…}
String={a,b,……,aa,ab,ac,……}
3.1 Preface
２,data structure
is a data object together with the relationships
among the instances and among the individual
elements that compose an instance
? Data_Structure={D,R}
? D---data object，
? R ---a set of relationships of all the data members in
D.
3.2 Linear List
L = (e1,e2,e3,…,en)
list size is n
if n=0,empty list
if n>0,
e1 is the first’th (or front) element
en is the last element
ei immediately precedes ei+1
3.2 Linear List
Example:
Students =(Jack,Jill,Abe,Henry,Mary,…,
Judy)
Exams =(exam1,exam2,exam3)
Days of Week = (S,M,T,W,Th,F,Sa)
Months = (Jan,Feb,Mar,Apr,…,Nov,Dec)
3.2 Linear List
Operations:
Create a linear list
determine whether the list is empty
determine the length of the list
find the kth of the element
search for a given element
delete the kth element
insert a new element just after the kth
3.2 Linear List
ADT specification of a linear list
AbstractDateType LinearList
{ instances
ordered finite collections of zero or more elements
operations
Create(); Destroy();
IsEmpty(); Length();
Find(k,x); Search(x);
Delete(k,x); Insert(k,x);
Output(out);
}
3.3 Formula-based Representation
1,Use an array to represent the instance of
an object
(e1,e2,………e n) length=n
each position of the array is called a cell or a
node
mapping formula:location(i)=i-1
e1 e2 e3 en
Element 0 1 2 n-1 maxsize-1
3.3 Formula-based Representation
2,Class definition,program 3.1
template <class T>
class LinearList{
public:
LinearList(int MaxListSize =10);
~ LinearList(){ delete [] element;};
bool IsEmpty() const {return length= =0;}
int Length() const (return length);
bool Find(int k,T&x) const;
int Search(const T&x) const;
LinearList <T>& Delete(int k,T&x);
LinearList <T>& Insert(int k,const T&x);
void Output(ostream& out) const;
private:
int length; int MaxSize; T* element;
}
3.3 Formula-based Representation
3,Operations:
1) Constructor,
template <class T>
LinearList<T>::LinearList(int MaxListSize)
{
MaxSize=MaxListSize;
element=new T[MaxSize];
length=0;
}
3.3 Formula-based Representation
2) bool Find(int k,T&x) O(1)
the k?th element in the list in x
L = (a,b,c,d,e)
find(1,x) = true,x=a
find(2,x) = true,x=b
find(4,x) = true,x=d
find(0,x) = error
find(9,x) = error
3.3 Formula-base Representation
program 3.3
template <class T>
bool LinearList<T>:,Find(int k,T &x) const
{ if (k<1|| k>length) return false;
x= element[k-1];
return true;
}
3.3 Formula-based Representation
3) search(const T&x) O(length)
return the index of x if found,otherwise return 0
L = (a,b,d,b,e)
search(d) = 3
search(a) = 1
search(z) = 0
3.3 Formula-based Representation
program 3.3
template <class T>
int LinearList <T>::Search(const T & x) const
{ for ( int i=0 ; i < length; i++)
if (element[i]==x) return ++i;
return 0;
}
3.3 Formula-based Representation
4) delete (int k,T&x)
delete the k’th element and return it in x
L = (a,b,c,d,e)
delete(2,x) =>
L=(a,c,d,e),x=b,
and index of c,d,e decrease by 1
delete(0,x) => error
delete(20,x) => error
3.3 Formula-based Representation
Program 3.4
template <class T>
LinearList <T>& LinearList <T>::Delete( int k,T & x)
{ if (Find(k,x))
{ for ( int i=k; i<length; i++)
element[i-1]=element[i];
length--;
return *this;
}
else throw OutOfBounds()
}
3.3 Formula-based Representation
5) insert (int k,const T&x)
insert x after the k?th element
L = (a,b,c,d,e,f,g)
insert(0,h) => L = (h,a,b,c,d,e,f,g)
index of a,b,c,d,e,f,and g increase by 1
insert(10,h) => error
insert(-6,h) => error
3.3 Formula-base Representation
Program 3.5:
template <class T>
LinearList <T> &LinearList <T>::insert(int k,const T &x)
{ if (k<0 || k> length ) throw OutOfBounds();
if ( length = = MaxSize) throw NoMem();
for ( int i= length-1; i>=k; i--)
element[i+1] = element[i] ;
element[k] = x ;
length++;
return *this;
}
3.3 Formula-based Representation
4,Let?s see an example using the class linear
list(program 3.7)
3.4 Linked Representation
1) Each node of a data object keeps a link or
a pointer about the location of other relevant
nodes
L=(e1,e2,………e n)
first
linked field …..,null
data field e1 e2 e3 en
3.4 Linked Representation
? The figure above is called a single linked
list,and the structure is also called a chain
? A chain is a linked list in which each node
represents one element.
? There is a link or pointer from one element
to the next.
? The last node has a null pointer.
3.4 Linked Representation
2,Classes Chain and ChainNode definition
program 3.8
template <class T> class ChainNode
{ friend Chain <T> ;
private:
T data;
chainNode<T> *link;
}
3.4 Linked Representation
template <class T> class Chain
{ public:
Chain( ){first=0;}
~Chain( );
bool IsEmpty( )const{ return first= =0;}
int Length( ) const;
bool Find(int k,T & x)const;
int Search(const T & x) const;
Chain<T>&Delete(int k,T& x);
Chain<T>&Insert(int k,const T& x);
void Output(ostream& out)const;
private,ChainNode<T> *first;
}
3.4 Linked Representation
3.operations
1)delete all the nodes in a chain
program 3.9
2)determine the length of a chain
program 3.10
3)find the kth element of a chain
program 3.11
3.4 Linked Representation
4)search for a chain
program 3.12
5)output a chain
program 3.13
3.4 Linked Representation
6) Deletion a element of a chain
a b c d e
null
first
first = first->link;
3.4 Linked Representation
first get to node just before node to be removed
before= first ->link;
a b d e
null
first
cc
before
3.4 Linked Representation
now change pointer in before
before ->link = before ->link ->link;
before
a b c d e
null
first
3.4 Linked Representation
Operation delete—program 3.14
template<class T>Chain<T>&Chain<T>::Delete(int k,T& x)
{ if( k<1|| !first)throw OutOfBounds( );
ChainNode<T> *p=first;
if ( k= = 1) first=first->link;
else
{ ChainNode<T> *q=first;
for (int index=1;index < k-1 && q ; index++)
q=q->link;
if (!q || !q->link) throw OutOfBounds( );
p = q->link; q->link = p->link;
}
x = p->data; delete p; return *this;
}
3.4 Linked Representation
a b c d e
nul
l
first
f
newNode
Step 1,get a node,set its data and link fields
ChainNode newNode =
new ChainNode(?f?,first);
7) insert operation ----insert(0,?f?)
3.4 Linked Representation
Step 2,update first
first = newNode;
a b c d e
null
first
f
newNode
3.4 Linked Representation
newNode->link=first;
first = newNode;
a b c d e
null
first
f
newNode
insert(3,?f?)
1,first find node whose index is 3
a b c d e
null
first
f
newNode
before
2,next create a node and set its data and link fields
ChainNode newNode = new ChainNode(?f?,before ->link);
3.finally link before to newNode
before->link = newNode;
Two-Step insert(3,?f?)
before = first ->link ->link;
newNode ->link = before ->link;
before ->link = newNode;
a b c d e
null
first
f
newNode
before
3.4 Linked Representation
Operation insert—program 3.15
template<class T>Chain<T>&Chain<T>::insert(int k,const
T& x)
{ if (k<0) throw OutOfBounds( );
ChainNode<T>*p = first;
for(int index = 1 ; index < k && p; index++)
p = p->link;
if (k>0 && !p) throw OutOfBounds( );
ChainNode<T>*y=new ChainNode<T>;
y->data = x;
if ( k) { y->link = p->link; p->link = y; }
else { y->link = first; first = y; }
return * this;
}
3.4 Linked Representation
4.Extensions to class chain
include some additional functions such as:
1)Erase—delete all nodes in a chain
2)Zero—set the first pointer to 0,but don?t
delete any node
3)Append—add an element to the end of a
chain.(to keep track of the last node in the chain,
we use a new private member ChainNode* last.)
3.5 simply linked Circular List
figure
a b c d e
first
3.5 Simply Linked Circular List
With Head Node
a b c d e
first
headNode
first
headNode
3.5 simply linked Circular List
For example:
Josephus Problem
n=8
m=3
3,6,1,5,2,8,4
7
1
2
3
4
5
6
7
8
3.5 simply linked Circular List
#include<iostream.h>
#include”CircList.h”
template<class T> void CircList<T>::
Josephus(int n,int m)
{ Firster( );
for (int i=0 ; i<n-1 ; i++)
{ for ( int j=0 ; j<m-1 ; j++) Next( );
cout<<“delete person”<<getdata( )<<endl;
remove( );
}
}
3.5 simply linked Circular List
void main( )
{ CircList <int> clist;
int n,m;
cout<<“Enter the Number of contestants?”;
cin>>n>>m;
for ( int i=1; i<=n; i++) clist.insert(i);
clist.Josephus(n,m);
}
3.6 Doubly Linked List
figure
a b c d e
null
firstNode
null
lastNode
3.6 Doubly Linked List
1,Class definition for doubly linked
list( program 3-21)
template<class T> class DoubleNode
{ friend DoubleNode<T>;
private:
T data;
DoubleNode<T>*left,*right;
}
template<class T> class Doubl
{ public:
Double( ){LeftEnd = RightEnd = 0;}
~Double( );
int Length( ) const;
bool Find(int k,T& x)const;
int Search(const T& x) const;
Double<T>&Delete(int k,T & x);
Double<T>& Insert( int k,const T & x);
void Output(ostream & out) const;
private:
DoubleNode<T>*LeftEnd,*RightEnd;
}
3.6 Doubly Linked List
2,Operations,Insert,Delete
3.6 Doubly Linked List
insert(0,?f?)
a b c d e
null
firstNode
null
lastNode
null
newNode firstNode->llink=newNode;
newNode->llink=null; newNode->rlink=firstNode;
firstNode=newNode
3.6 Doubly Linked List
Insert(2,?f?)
a b c d e
null
firstNode
null
lastNode
beforeNode
newNode
newNode->llink=beforeNode; newNode->rlink=beforeNode->rlink;
beforeNode->rlink->llink=newNode; beforeNode->rlink=newNode;
3.6 Doubly Linked List
Delete(1)
a b c d e
null
firstNode
null
lastNode
P=firstNode; firstNode=p->rlink; firstNode->llink=null;
p
null
3.6 Doubly Linked List
Delete(3)
a b c d e
null
firstNode
null
lastNode
p
P->llink->rlink=p->rlink;
P->rlink->llink=p->llink;
Double Linked Circular List
figure
a b c d e
firstNode
Doubly Linked Circular List
With Header Node
figure
a b c e
headerNode
d
Empty Doubly Linked Circular
List With Header Node
headerNode
3.7 simulating pointer
A:
