Introduction
Dynamic Data Structures
Grow and shrink at execution time
Linked lists are dynamic structures where
data items are “linked up in a chain”
Insertions and deletions can be made anywhere
Stacks and queues can be implemented using either
Singly linked list, or
Doubly linked list
Singly Linked Lists
Self-referential class
A self-referential class
contains an instance variable that refers to another object
of the same class type.
For example, the generic class declaration
class SNode< T >
{
private T data;
private SNode<T> nextNode; // reference to next node
public SNode( T data ) { /* constructor body */ }
public void setData( T data ) { /* method body */ }
public T getData() { /* method body */ }
public void setNext( SNode<T> next ) { /* method body */ }
public SNode<T> getNext() { /* method body */ }
} // end class SNode< T >
declares class Snode<T>, which has
two private instance variables
data (of the generic type T) and SNode<T> variable nextNode.
Singly Linked Lists
A linked list is a linear collection (i.e., a sequence)
of self-referential-class objects, called nodes,
connected by reference links—hence, the term “linked” list.
Typically, a program accesses a singly linked list via either
a reference to its first node called head, or
a reference to its last node called tail
By convention, the link reference in the last node of the list
is set to null.
Singly Linked Lists (Cont’d)
A linked list is appropriate when the number
of data elements to be represented in the data structure
is unpredictable.
Refer to SinglyLinkedListApp project
Singly Linked Lists (Cont’d)
The SinglyLinkedList<T> class
Implements the SList<T> interface containing
int size(), boolean isEmpty()
void insertAtHead(T e), void insertAtTail(T e)
T removeFromHead() , and T removeFromTail() methods
Then, used to implement the
Stack data structures, through SListBasedStack class
and queue data structure, through SListBasedQueue class
Doubly Linked Lists
Doubly Linked List
A doubly linked list models
a sequence of “objects” storing arbitrary objects
It establishes a before/after relation between “objects”
header nodes/positions trailer
elements
DNode<T> class
It represents a node in doubly linked list
What are the properties of these “Nodes”?
They hold a
a reference to an element object
a reference to previous DNode<T>
and a reference to next DNode<T>
Important : it defines the relative position
Before, After, First, Last
DNode<T> class (Cont’d)
The DNode
models the notion of a “place” in a list
Within a data structure where a single object is stored
gives a unified view of diverse ways of storing data
in a doubly linked list
Abstracts a node of a linked list (double or single)
public class DNode<T> {
public T element;
public DNode<T> next;
public DNode<T> prev;
….
}
Dlist<T> ADT
Accessor methods:
The Dlist<T> ADT models a first(), last()
sequence of positions storing
arbitrary objects prev(DNode<T>), next(DNode<T>)
It establishes a before/after
relation between positions
Update methods:
replaceElement(DNode<T>, T)
swapElements (DNode<T>, T)
Generic methods:
size(), isEmpty() insertBefore(DNode<T>, T),
insertAfter(DNode<T>, T),
Query methods
isFirst(DNode<T>), insertFirst(T), insertLast(T)
isLast(DNode<T>)
remove(T)
Doubly Linked List
implementation
A doubly linked list
prev next
provides a natural implementation of the Dlist<T> ADT
Nodes of list store:
element
link to the previous node
link to the next node elem node
Has special trailer and header nodes
Refer to DoublyLinkedListApp project
header nodes/positions trailer
elements
Insertion
We visualize operation insertAfter(DNode<T> p, T X), which returns Dnode<T> q
p
A B C
p
A B q C
X
p q
A B X C
Insertion Algorithm
Algorithm insertAfter(p,e):
Create a new node v
[Link](e)
[Link](p) {link v to its predecessor}
[Link]([Link]()) {link v to its successor}
([Link]()).setPrev(v) {link p’s old successor to v}
[Link](v) {link p to its new successor, v}
return v {the position for the element e}
Deletion
We visualize remove(p), where p = last()
p
A B C D
A B C p
A B C
Deletion Algorithm
Algorithm remove(p):
t = [Link] {a temporary variable to hold the return value}
([Link]()).setNext([Link]()) {linking out p}
([Link]()).setPrev([Link]())
[Link](null) {invalidating the position p}
[Link](null)
return t