Transcript Linked list

CSCI 3333 Data Structures
Linked Lists
by
Dr. Bun Yue
Professor of Computer Science
[email protected]
http://sce.uhcl.edu/yue/
2013
Acknowledgement




Mr. Charles Moen
Dr. Wei Ding
Ms. Krishani Abeysekera
Dr. Michael Goodrich
Static Data Structures


The size of static data structures do
not change.
Example: array. During runtime, if
there are more elements to be
stored in an array:




A new array needs to be created.
The old array may be deleted.
Elements are copied.
Expensive!
Dynamic Data Structures


The size of a dynamic data structure
can change during runtime.
Many applications need to use
dynamic data structures.
Linked List ADT


A linked list is a sequence of nodes linked
in a chain.
Some operations:








Create
Delete
Traverse
Insert a node
Delete a node
Insert a linked list
Delete a linked list
…
Linked Lists vs. Arrays

Advantages:



Dynamic: size changes on demand.
Insertion and deletion of nodes: can be
faster in some situations.
Disadvantages:


May not be randomly accessible
efficiently.
Options:
Programmers needs to manage memory.
 Automatic garbage collection may bring
performance issues.

Linked List ADT



There are many kinds of linked lists
implemented by different
languages.
They are different ADTs.
We can study the ADTs to use them
without knowing how they are
implemented.
Example: C++ STL list

Some methods:






begin: returns an iterator addressing the first
element in a list.
pop_back:deletes the element at the end of a
list.
pop_front: deletes the element at the
beginning of a list.
push_back: adds an element to the end of a
list.
push_front: adds an element to the beginning
of a list.
…
Example Program
#include <list>
#include <iostream>
using namespace std ;
typedef list<int> INT_LIST;
int main()
{
INT_LIST ilist;
ilist.push_back(1);
ilist.push_front(2);
ilist.push_front(3);
ilist.push_front(4);
ilist.push_back(5);
cout << ilist.front() << endl;
cout << ilist.back() << endl;
Example Program (cont)
INT_LIST::iterator i;
cout << "Int list content:";
for (i = ilist.begin(); i != ilist.end(); ++i)
cout << " " << *i; // Note *
cout << endl;
for (i = ilist.begin(); i != ilist.end(); ++i)
(*i)++;
cout << "Int list content:";
for (i = ilist.begin(); i != ilist.end(); ++i)
cout << " " << *i; // Note *
cout << endl;
}
ilist.pop_front();
ilist.pop_back();
cout << "Int list content:";
for (i = ilist.begin(); i != ilist.end(); ++i)
cout << " " << *i; // Note *
cout << endl;
Output 1
ilist.push_back(1);
ilist.push_front(2);
ilist.push_front(3);
ilist.push_front(4);
ilist.push_back(5);
cout << ilist.front() << endl;
cout << ilist.back() << endl;
Output:
4
5
Output 2
INT_LIST::iterator i;
cout << "Int list content:";
for (i = ilist.begin(); i != ilist.end(); ++i)
cout << " " << *i;
// Note *
cout << endl;
for (i = ilist.begin(); i != ilist.end(); ++i)
(*i)++;
cout << "Int list content:";
for (i = ilist.begin(); i != ilist.end(); ++i)
cout << " " << *i;
// Note *
cout << endl;
Output:
Int list content: 4 3 2 1 5
Int list content: 5 4 3 2 6
Output 3
ilist.pop_front();
ilist.pop_back();
cout << "Int list content:";
for (i = ilist.begin(); i != ilist.end(); ++i)
cout << " " << *i;
cout << endl;
Output:
Int list content: 4 3 2
Perl Example




In Perl, an array is also a list.
It is built into the language. (You
can see the importance of lists
here.)
Array/List variables start with the
symbol @, e.g. @a.
List elements are scalar (which
starts with the symbol $), e.g.
$a[1], $a[12], etc.
Perl’s List Examples
@num[1,2] = (3,4); # $num[1] = 3; $num[2] = 4;
@num[1,2] = @num[2,1];
# swap $num[1] and $num[2];
@num[1,2] = @num[3,3];
# $num[1] = $num[3]; $num[2] = $num[3];
($num[1], $num[2]) = ($num[2], $num[1]);
# swap $num[1] and $num[2];
@num = (1,2,3,4,5)[3,2,1]; # @num = (4,3,2);
($first, @num) = @num;
# remove the first element of @num into $first
(@num, $last) = @num;
# pop the last element to $last
Java’s List Interface ADT


Java has a List interface for ordered collection
(sequence).
Super-interface:



Some known implementation classes:






Collection
Iterable
AbstractList
LinkedList
ArrayList
Vector
…
Practical APIs are much richer than those found in
some textbooks!
Interable Interface
Target of a for each statement.
 One method only
Iterator<T>iterator(): returns an
iterator over a set of elements of
type T.
 Iterator<T> interface’s methods:




hasNext()
next()
remove()
Collection Interface



Group of objects, possibly with duplicates.
Super-interface: iterable.
Some methods:








add(E e)
addAll(Collection<? extends E> c)
contains(Object o)
remove(Object o)
removeAll(Collection<?> c)
size()
toArray()
…
List Interface

New required methods added:

Random access:
E get(int index)
 E remove(int index)


Searching:
int indexOf(Object o)
 int lastIndexOf(Object o)


List Iterator:

ListIterator<E> listIterator()
Concrete Class LinkedList<E>

Interface implemented:





Serializable
Cloneable
Iterable<E> Collection<E> 
Queue<E>  Deque<E>
Iterable<E>  Collection<E> 
List<E>
<E>: Actual E should be a class
(not int, float, etc)
LinkedList Methods

From implementing Dequeue:







void addFirst(E e)
void addLast(E e)
E removeFirst()
E removeLast()
E offerFirst(): retrieve, not remove,
exception version for empty Dequeue.
E peekFirst(): retrieve, not remove,
return null version for empty Dequeue.
…
LinkedList Methods

From implementing List:





add(E e)
E get(int index)
E remove(int index)
remove(Object o)
int indexOf(Object o)
Finding the Right Structures




APIs are usually feature rich.
Study purposes of classes and
interfaces.
Study hierarchical class and
interface structures.
Study methods available.
Examples

Good to critically read program
code.


http://www.javasamples.com/showtutorial.php?tutoriali
d=347
http://www.idevelopment.info/data/Pro
gramming/java/collections/LinkedListEx
ample.java
Implementation Issues


You do not need to know how classes are
implemented to use them!
However, knowing the implementations:



May deepen understanding of the classes for
better usages.
May help selecting the best class for the
application.
May transfer this knowledge when you need to
implement custom-designed classes yourself.
Example Implementation in C++

Singly linked list of float




Each node has only one pointer to its
successor.
The list stores a head pointer to the
head of the list.
If the list is empty, the head pointer is
null.
For simplicity, each node stores an
float.
Implementation issues

Data members:





Value of float
head pointer
tail pointer: for efficiency
size of the list: for efficiency.
Tips: ensure all data members
properly updated in operations.
Node

class FloatList{
private:
// Declare a structure for the list.
// Simliar to nested classes in Java
struct ListNode
{
float value;
struct ListNode *next; };
ListNode *head, *tail;
// head and tail pointers
int _size;
Method Prototypes
public:
FloatList() // Constructor
{
head = tail = NULL;
_size = 0;
}
~FloatList(); // Destructor

Tips: always include constructors and
destructors.
Method Prototypes
void appendTailNode(float);
// insert node at the tail.
bool deleteHeadNode();
// delete node at the head.
bool deleteNode(float);
// delete the first occurrence of the float
// list.
void displayList();
int size() { return _size; }
bool isEmpty() { return _size == 0; }
};
Method Implementations
void FloatList::appendTailNode(float num)
{ ListNode *newNode;
// Allocate a new node & store num
newNode = new ListNode;
newNode->value = num;
newNode->next = NULL;
}
if (head==NULL)
{
// empty list
head = tail = newNode;
}
else
{
tail->next = newNode;
tail = tail-> next;
}
_size++;
Discussion



Maintenance of data members.
Trade off of using _size and tail:
faster for some operations and
slower for others.
Definition of newNode as class
instead of struct: use of
constructors.
deleteHeadNode
bool FloatList::deleteHeadNode() {
if (head == NULL)
return false;
else
{ ListNode *temp = head;
head = head-> next;
if (head == NULL) tail = NULL;
delete temp;
_size--;
return true;
}
}
Discussion

Other possible methods:


deleteTailNode
May change prototype:
deleteNode(float f)
bool FloatList::deleteNode(float f) {
if (head == NULL)
return false;
else
{ ListNode *curr = head;
ListNode *prev = NULL;
while (curr != NULL && curr->value != f)
{
prev = curr;
curr = curr-> next;
}
}
if (curr == NULL) // do not find the number to be
deleted.
return false;
else // to be continued.
}
else part
{
if (prev == NULL)
{
// the head node contains the number.
head = curr-> next;
}
if (curr == tail)
{
// the tail node will be deleted.
tail = prev;
}
// link the prev node to skip the curr node.
prev->next = curr->next;
}
delete curr;
_size--;
return true;
Discussion

Other possible methods.

deleteLastNode.
displayList
void FloatList::displayList()
{
ListNode *nodePtr;
nodePtr = head;
while (nodePtr)
{
cout << nodePtr->value << " ";
nodePtr = nodePtr->next;
}
cout << endl;
}
Discussion


Not flexible.
Need an ‘iterator’.
Destructor
FloatList::~FloatList(){
ListNode *curr, *next;
curr = head;
while (curr != NULL){
next = curr->next;
delete curr;
curr = next;
}
}
Test Program
FloatList list;
list.appendTailNode(2.2);
list.appendTailNode(3.4);
list.appendTailNode(2.2);
list.appendTailNode(1.8);
list.appendTailNode(2.2);
list.displayList();
cout << "size: " << list.size() << endl;
Output:
2.2 3.4 2.2 1.8 2.2
size: 5

Test Program
list.deleteHeadNode();
list.displayList();
cout << "size: " << list.size() << endl;
list.deleteNode(2.2);
list.displayList();
cout << "size: " << list.size() << endl;
list.deleteNode(2.2);
list.displayList();
cout << "size: " << list.size() << endl;
Outpit:
3.4 2.2 1.8 2.2
size: 4
3.4 1.8 2.2
size: 3
3.4 1.8
size: 2

Test Program
list.deleteHeadNode();
list.deleteHeadNode();
list.displayList();
cout << "size: " << list.size() << endl;

Output:
size: 0
Discussion

Other possible methods:




getHeadNodeValue()
getTailNodeValue()
deleteTailNode()
…
Discussion

Some operations, deleteTailNode
may take longer time, O(N), where
N is the number of nodes in the list.



May use a doubly linked list.
Need to have a way to analyze
performance.
List only works for float

May use template.
Questions and Comments?