Transcript First

Data Structures
4
Lists and Linked List Data
Structures
Prof A Alkhorabi
Overview
•
•
•
•
•
List concepts.
List applications.
A list ADT: requirements, contract.
Implementations of lists: using arrays, linked lists.
Linked lists: singly-linked
– Insertion.
– Deletion.
– List Traversal
• Doubly-linked Lists
Prof A Alkhorabi
4- 2
List concepts (1)
• A list is a sequence of elements, whose order is significant.
Elements can be added and removed anywhere in the list.
• The length of a list is the number of elements it contains.
• An empty list has length zero.
• The concatenation of lists l1 and l2 is a list containing all
the elements of l1 followed by all the elements of l2.
• Traversal of a list (or iterating over a list) means visiting
each of the list’s elements in turn, in some desired order.
Prof A Alkhorabi
4- 3
List concepts (2)
• Notation for lists: «a, b, …, z». The empty list is « ».
– List notation is used here, but not supported by C++.
• Examples of lists:
fibonacci = «1, 1, 2, 3, 5, 8, 13, 21, 44, 65»
birthdays = «2001-02-23, 2001-05-05, 2001-11-05»
tour
= «GLA, LHR, CDG, GLA»
hamlet1 = «‘to’, ‘be’, ‘or’, ‘not’, ‘to’, ‘be’»
hamlet2 = «‘that’, ‘is’, ‘the’, ‘question’»
• Concatenation of hamlet1 and hamlet2:
«‘to’, ‘be’, ‘or’, ‘not’, ‘to’, ‘be’, ‘that’, ‘is’, ‘the’, ‘question’»
Prof A Alkhorabi
4- 4
Lists vs. linked lists
1 ‫جواب‬
• Do not confuse the list ADT with a linked-list data
structure.
• A list ADT can be implemented using different data
structures (arrays, linked lists).
• Linked-list data structures can be used to implement many
ADTs (e.g., stacks, queues, sets).
Prof A Alkhorabi
4- 5
List applications
• A sentence is a list of words.
– The order of words is significant.
– The same word can occur more than once in a sentence.
• An itinerary is a list of places visited on a tour.
– The order of places is significant.
– The same place can occur more than once in an
itinerary.
• A log is a list of event records (e.g., equipment faults).
– The event records are in time order.
Prof A Alkhorabi
4- 6
Example: simple text editor (1)
• Consider a simple text editor that supports insertion and
deletion of complete lines only.
• The user can load text from a file, or save the text to a file.
• The user can select any line of the text:
– directly (e.g., by a mouse-click)
– by searching for the next line matching a given search
string.
• The user can delete the selected line.
• The user can insert a new line, either before or after the
selected line.
Prof A Alkhorabi
4- 7
Example: simple text editor (2)
• We can represent the text being edited by:
– a list of lines, text
– the number of the selected line, sel
(where 0  sel < length of text lines, or sel = –1 if text is empty)
• We can implement the user commands straightforwardly in terms of
list operations, e.g.:
– Delete: remove line sel of text.
– Insert before: add the new line as line sel of text, then increment
sel.
– Insert after: increment sel, then add the new line as line sel of
text.
– Save: traverse text, writing each line to the output file.
Prof A Alkhorabi
4- 8
List ADT: requirements
2 ‫جواب‬
Requirements:
1) It must be possible to make a list empty.
2) It must be possible to test whether a list is empty.
3) It must be possible to obtain the length of a list.
4) It must be possible to add an element anywhere in a list.
5) It must be possible to remove an element anywhere in a list.
6) It must be possible to inspect or update an element anywhere
in a list.
7) It must be possible to concatenate lists.
8) It must be possible to test lists for equality.
9) It must be possible to traverse a list.
Prof A Alkhorabi
4- 9
List ADT: contract (1)
• Possible contract:
class List {
// Each List object is an indexed list whose
// elements are objects.
////////// Accessors //////////
bool IsEmpty ();
// Return true if and only if this list is empty.
int Size ();
// Return this list’s length.
Prof A Alkhorabi
4- 10
List ADT: contract (2)
Possible contract (continued):
void Get (int i);
// Return the element with index i in this list.
bool Equals (List that);
// Return true if and only if this list and that list have the
// same length, and each element of this list equals the
// corresponding element of that.
Prof A Alkhorabi
4- 11
List ADT: contract (3)
• Possible contract (continued):
//////////// Transformers ////////////
void Clear ();
// Make this list empty.
void Set (int i, Elem elem);
// Replace the element at index i in this list by elem.
// The element could be a structure or a single piece of Info
void Add (int i, Elem elem);
// Add elem as the element with index i in this list.
void Add (Elem elem);
// Add elem after the last element of this list.
Prof A Alkhorabi
4- 12
List ADT: contract (4)
• Possible contract (continued):
void AddAll (List that);
// Add all the elements of that after the last element of
// this list.
void Del (int i);
// Remove the element with index i in this list.
}
Prof A Alkhorabi
4- 13
List traversal
4 ‫جواب‬
• Traverse a data structure is to visit its components
(elements, nodes), almost serially
• To traverse array a:
for (int i = 0; i < a.Length; i++)
… a[i] …
• We could mimic this to traverse list:
for (int i = 0; i < list.Size(); i++)
… list.Get(i) …
… list.Set(i, x) …
This traversal has time complexity O(n2),
if Get and Set is O(n) each.
Prof A Alkhorabi
4- 14
Linked Data Structures
• Linked data structures (or simply data structures),
are structures represent objects linked in one of the
following types:
• Linear data structures:
– Linked lists: single, double, circular.
– Stack.
– Queue.
• Non-Linear data structures :
– Tree: binary, multi-branch.
– Graph.
Prof A Alkhorabi
4- 15
Implementation
• Any of the above mentioned data structures
can also be implemented in one of the
following ways:
– Arrays
– Pointers (known as linked list method)
Prof A Alkhorabi
4- 16
Implementation of lists using SLLs
• Represent an (unbounded) list by:
– a variable length
– a SLL, with links first and last to both ends:
first element
Invariant:
element
last element
element
element
Empty list:
Illustration:
Prof A Alkhorabi
GLA
LHR
CDG
GLA
4- 17
Linked lists (1)
• A linked list consists of a sequence of nodes connected by
links, plus a header.
• Each node (except the last) has a successor, and each node
(except the first) has a predecessor.
• Each node contains a single element (object or value), plus
links to its successor and/or predecessor.
ant
header
node
ant
Prof A Alkhorabi
bat
element
bat
cat
link
null link
cat
4- 18
Linked lists (2)
• The length of a linked list is the number of
nodes.
• An empty linked list has no nodes.
• In a linked list:
– We can manipulate the individual elements.
– We can manipulate the links, thus changing the
linked list’s very structure! (This is impossible
in an array.)
Prof A Alkhorabi
4- 19
Singly-linked lists (1)
• A singly-linked list (SLL) consists of a sequence of
nodes, connected by links in one direction only.
• Each SLL node contains a single element, plus a link to the
node’s successor (or a null link if the node has no
successor).
• A SLL header contains a link to the SLL’s first node (or a
null link if the SLL is empty).
pig
dog
cat
rat
dog
Prof A Alkhorabi
4- 20
Singly-linked lists (2)
• A C++ structure is used to implement a SLL node:
// SLL Node declaration
struct SLLNode{
char Data[10];
// Node Information
SLLNode* Next; // Node Communication (SLL-Link)
};
Prof A Alkhorabi
4- 21
Singly-linked lists (3)
• A C++ class is used to implement the Single
Linked List:
// SLL declaration
class SingleLinkedList {
private: SLLNode *First, *Last;
int Length;
public:
//////////// Constructor ////////////
SingleLinkedList () { First = Last = NULL; Length = 0;} ;
…
};
SLL methods (to follow)
Prof A Alkhorabi
4- 22
Example: SLL traversal
• A method (in class SLL) to traverse an SLL:
// Traverse the SLL and print its Nodes
void SingleLinkedList::PrintList(){
SLLNode* curr = First; // Start from first node
while(curr){ cout << curr -> Data << " "; curr = curr -> Next;
}
cout << endl;
}
• Animation:
first
First
ant
bat
cat
curr
Prof A Alkhorabi
4- 23
Example: SLL manipulation (Swaping)
• A method (in class SLL) to swap an SLL’s first and second nodes:
void swapFirstTwo () {
// Swap this SLL’s 1st and 2nd nodes (assuming length > 1).
SLLNode* Second;
Second = First -> Next;
First -> Next = Second -> Next;
Second -> Next = First;
First = Second;
}
• Animation:
first
First
ant
bat
cat
second
Second
Prof A Alkhorabi
4- 24
Insertion
• Problem: Insert a new element at a given point in a linked list.
• Four cases to consider:
1) insertion in an empty linked list;
2) insertion before the first node of a nonempty linked list;
3) insertion after the last node of a nonempty linked list;
4) insertion between nodes of a nonempty linked list.
• The insertion algorithm needs links to the new node’s successor
and predecessor.
• We will consider case 2 and 4 in our SLL.
Prof A Alkhorabi
4- 25
SLL insertion (1)
• SLL insertion algorithm:
To insert elem at a given point in the SLL headed by First:
1. Make ins a link (pointer) to a newly-created node with
element elem and successor null.
2. If the insertion point is before the first node:
2.1.
Set node ins’s successor to first.
2.2.
Set first to ins.
3. If the insertion point is before the node pred:
3.1.
Set node ins’s successor to node pred’s
successor.
3.2.
Set node pred’s successor to ins.
4. Terminate.
Prof A Alkhorabi
4- 26
SLL insertion (2)
• Animation (insertion before first node):
To insert elem at a given point in the SLL headed by first:
1. Make ins a link to a newly-created node with element
elem and successor null.
2. If the insertion point is before
thefirst
firstnode:
node:
after the
2.1.
2.1. Set
Set node
node ins’s
ins’s successor
successor to
to first.
first.
2.2.
2.2. Set
Set first
first to
to ins.
ins.
3.
3. If
If the
the insertion
insertion point
point is
is after
after the
the node
node pred:
pred:
3.1.
3.1. Set
Set node
node ins’s
ins’s successor
successor to
to node
node pred’s
pred’s successor.
successor.
3.2.
3.2. Set
Set node
node pred’s
pred’s successor
successor to
to ins.
ins.
4.
4. Terminate.
Terminate.
first
ins
Prof A Alkhorabi
bat
cat
ant
4- 27
SLL insertion (3)
• Animation (insertion after intermediate node):
To insert elem at a given point in the SLL headed by first:
1. Make ins a link to a newly-created node with element
elem and successor null.
2. If the insertion point is before
thefirst
firstnode:
node:
after the
2.1.
2.1. Set
Set node
node ins’s
ins’s successor
successor to
to first.
first.
2.2.
2.2. Set
Set first
first to
to ins.
ins.
3.
3. If
If the
the insertion
insertion point
point is
is after
after the
the node
node pred:
pred:
3.1.
3.1. Set
Set node
node ins’s
ins’s successor
successor to
to node
node pred’s
pred’s successor.
successor.
3.2.
3.2. Set
Set node
node pred’s
pred’s successor
successor to
to ins.
ins.
4.
4. Terminate.
Terminate.
first
pred
Prof A Alkhorabi
dog
ins
fox
eel
4- 28
SLL insertion (4)
The following C++ inserting method adds a node at the end of SLL:
void Add(char* c)
{
SLLNode* p;
// 1. Declare a pointer to the node type
p = new SLLNode; // 2. Allocate memory to the new node
// 3. Fill Node
strcpy( p -> Data, c);
p -> Next = NULL;
// 4. Link the Filled Node to the Linked List
if(Length == 0)
First = p;
// If SLL is empty p will be the first
else
Last->Next = p;
// Otherwise put p after Last
Last=p;
Length++;
}Prof A Alkhorabi
4- 29
Deletion
• Problem: Delete a given node from a linked list.
• Three cases to consider for deletion of a singleton
node;
1) deletion of the first node;
2) deletion of the last node;
3) deletion of an intermediate node.
• The deletion algorithm needs links to the deleted
node’s successor and predecessor.
• We will consider case 1 and 3 in our SLL.
Prof A Alkhorabi
4- 30
SLL deletion (1)
• SLL deletion algorithm:
To delete node del from the SLL headed by first:
1. Let succ be node del’s successor.
2. If del = first:
2.1. Set first to succ.
3. Otherwise (if del  first):
3.1. Let pred be node del’s predecessor.
3.2. Set node pred’s successor to succ.
4. Terminate.
• But there is no link from node del to its predecessor, so step
3.1 can access del’s predecessor only by following links
from first!
Prof A Alkhorabi
4- 31
SLL deletion (2)
• Animation (deleting the first node):
To delete node del from the SLL headed by first:
1. Let succ be node del’s successor.
2. If del = first:
2.1. Set first to succ.
3. Otherwise (if del  first):
3.1. Let pred be node del’s predecessor.
3.2. Set node pred’s successor to succ.
4. Terminate.
first
del
Prof A Alkhorabi
ant
succ
bat
cat
garbage
4- 32
Example: SLL manipulation (1)
• Instance method (in class SLL) to delete an SLL’s first
node:
void DeleteFirst () {
// Delete this SLL’s first node (assuming length > 0).
First = First -> Next;
}
• Animation:
first
First
Prof A Alkhorabi
ant
bat
cat
4- 33
SLL deletion (3)
• Animation (deleting an intermediate (or last) node):
To delete node del from the SLL headed by first:
1. Let succ be node del’s successor.
2. If del = first:
2.1. Set first to succ.
3. Otherwise (if del  first):
3.1. Let pred be node del’s predecessor.
3.2. Set node pred’s successor to succ.
4. Terminate.
first
dog
pred
Prof A Alkhorabi
del
eel
succ
fox
garbage
4- 34
Example: SLL manipulation (2)
• Instance method (in class SLL) to delete an SLL’s second
node:
void deleteSecond () {
// Delete this SLL’s second node (assuming length > 1).
SLLNode* Second;
Second = First -> Next;
First -> Next = Second -> Next;
}
• Animation:
first
First
ant
bat
cat
second
Second
Prof A Alkhorabi
4- 35
SLL deletion (4)
• Analysis:
Let n be the SLL’s length.
Step 3.1 must visit all nodes from the first node to the
deleted node’s predecessor. There are between 0 and n–1
such nodes.
Average no. of nodes visited = (n – 1)/2
Time complexity is O(n).
Prof A Alkhorabi
4- 36
SLL deletion (5)
• The following method deletes the node of an SLL which
carry the string similar to what is pointed to by c pointer:
void SingleLinkedList::Del(char* c)
{
SLLNode* p=First, *q;
if( !strcmp (p->Data, c)) { First=First->Next; delete p; Length--; }
else{ while (p){
q = p; p = p->Next;
if( !strcmp (p->Data, c)) { q->Next=p->Next; delete p; p=NULL;
Length--; } } }
}
Example: SLL_CPP.CPP
Prof A Alkhorabi
4- 37
The SLL class can be tested through the following main() function:
void main()
{
SingleLinkedList SLL1;
//1
SLL1.Add("Salem");
SLL1.PrintList();
//2
cout<< "No of nodes in SLL = " << SLL1.size() << endl;
SLL1.Add("Ahmed"); SLL1.PrintList();
//3
SLL1.Add("Ali");
SLL1.PrintList();
//4
SLL1.Add("Omar");
SLL1.PrintList();
//5
cout<< "No of nodes in SLL = " << SLL1.size() << endl << endl;
cout<< "Person in First node of SLL is " << SLL1.get(0) << endl;
cout<< "Person in Second node of SLL is " << SLL1.get(1) << endl;
cout<< "Person in Third node of SLL is ” << SLL1.get(2) << endl;
cout<< "Person in Fourth node of SLL is " << SLL1.get(3) << endl << endl;
SLL1.Del("Salem"); SLL1.PrintList();
//6
SLL1.Del("Ali"); SLL1.PrintList();
//7
cout<< "No of nodes in SLL = " << SLL1.size() << endl;
}
Prof A Alkhorabi
4- 38
The Output is:
Salem
No of nodes in SLL = 1
Salem Ahmed
Salem Ahmed Ali
Salem Ahmed Ali Omar
No of nodes in SLL = 4
Person in First node of SLL is
Person in Second node of SLL is
Person in Third node of SLL is
Person in Fourth node of SLL is
Salem
Ahmed
Ali
Omar
Ahmed Ali Omar
Ahmed Omar
No of nodes in SLL = 2
Prof A Alkhorabi
4- 39
Doubly-linked lists (1)
• A doubly-linked list (DLL) consists of a sequence of
nodes, connected by links in both directions.
• Each DLL node contains a single element, plus links to the
node’s successor and predecessor (or null link(s)).
• The DLL header contains links to the DLL’s first node (or
null link if the DLL is empty).
pig
dog
cat
rat
dog
Prof A Alkhorabi
4- 40
Doubly-linked lists (2)
• C++ structure implementing DLL node:
// DLL Node declaration
struct DLLNode{
char Data[10];
// Node Information
DLLNode * Next, *Pred; // Node Communication (DLL-Link)
};
Prof A Alkhorabi
4- 41
Doubly-linked lists (3)
• C++ class implementing a DLL:
// DLL declaration
class DoubleLinkedList {
private: DLLNode *First, *Last;
int Length;
public:
//////////// Constructor ////////////
DoubleLinkedList () { First = Last = NULL; Length = 0; } ;
…
};
Prof A Alkhorabi
DLL methods (to follow)
4- 42
Example: DLL traversal
• Instance method (in class DLL) to traverse a DLL, from last
node to first:
public void printLastToFirst () {
// Print all elements in this DLL, in last-to-first order.
for (DLLNode curr = Last;
curr != Null; curr = curr -> pred)
cout << curr-> Data;
}
• Animation:
First
first
last
Last
ant
bat
cat
curr
Prof A Alkhorabi
4- 43
Example: DLL manipulation (1)
• Instance method (in class DLL) to delete a DLL’s first node:
public void deleteFirst () {
// Delete the DLL’s first node (assuming length > 0).
DLLNode *Second;
Second = First -> Next;
Second -> Pred = Null;
First = Second;
}
• Animation:
First
first
last
Last
ant
bat
cat
second
Second
Prof A Alkhorabi
4- 44
Example: DLL manipulation (2)
• Instance method (in class DLL) to delete a DLL’s last node:
public void deleteLast () {
// Delete this DLL’s last node (assuming length > 0).
DLLNode* Last2;
Last2 = Last -> Pred;
Last2 -> Next = Null;
Last = Last2;
}
• Animation:
First
first
last
Last
ant
bat
cat
Last2
Prof A Alkhorabi
4- 45
DLL insertion (4)
• Animation (insertion before the first node):
To insert elem at a given point in the DLL headed by (first, last):
1. Make ins a link to a newly-created node with element elem,
predecessor null, and successor null.
2. Insert ins at the insertion point in the forward SLL headed by first.
3. Let succ be ins’s successor (or null if ins has no successor).
4. Insert ins after node succ in the backward SLL headed by last.
5. Terminate.
ins
first
last
ant
bat
cat
succ
Prof A Alkhorabi
4- 46
DLL insertion (5)
• Animation (insertion after the last node):
To insert elem at a given point in the DLL headed by (first, last):
1. Make ins a link to a newly-created node with element elem,
predecessor null, and successor null.
2. Insert ins at the insertion point in the forward SLL headed by first.
3. Let succ be ins’s successor (or null if ins has no successor).
4. Insert ins after node succ in the backward SLL headed by last.
5. Terminate.
dog
ins
first
last
bat
cat
succ
Prof A Alkhorabi
4- 47
DLL insertion (6)
• Animation (insertion between nodes):
To insert elem at a given point in the DLL headed by (first, last):
1. Make ins a link to a newly-created node with element elem,
predecessor null, and successor null.
2. Insert ins at the insertion point in the forward SLL headed by first.
3. Let succ be ins’s successor (or null if ins has no successor).
4. Insert ins after node succ in the backward SLL headed by last.
5. Terminate.
eel
ins
first
last
dog
fox
succ
Prof A Alkhorabi
4- 48
DLL deletion (1)
• DLL deletion algorithm:
To delete node del from the DLL headed by (first, last):
1. Let pred and succ be node del’s predecessor and
successor.
2. Delete node del, whose predecessor is pred, from the
forward SLL
headed by first.
3. Delete node del, whose successor is succ, from the
backward SLL
headed by last.
4. Terminate.
Prof A Alkhorabi
4- 49
DLL deletion (2)
• Animation (deleting the first (but not last) node):
To delete node del from the DLL headed by (first, last):
1. Let pred and succ be node del’s predecessor and successor.
2. Delete node del, whose predecessor is pred, from the forward
SLL headed by first.
3. Delete node del, whose successor is succ, from the backward SLL
headed by last.
4. Terminate.
del
first
last
pred
Prof A Alkhorabi
ant
bat
cat
succ
4- 50
DLL deletion (3)
• Animation (deleting an intermediate node):
To delete node del from the DLL headed by (first, last):
1. Let pred and succ be node del’s predecessor and successor.
2. Delete node del, whose predecessor is pred, from the forward
SLL headed by first.
3. Delete node del, whose successor is succ, from the backward SLL
headed by last.
4. Terminate.
del
first
last
pred
Prof A Alkhorabi
dog
eel
fox
succ
Example: DLL_CPP.cpp
4- 51
Comparison of insertion and deletion
algorithms
Algorithm
SLL
DLL
Insertion
Deletion
O(1)
O(n)
O(1)
O(1)
Prof A Alkhorabi
4- 52