Linked Representation lists elements are stored, in memory, in an arbitrary order
explicit information (called a link) is used to go from one element to the next
Memory Layout a b c d e c a e d b A linked representation uses an arbitrary layout. Layout of L = (a,b,c,d,e) using an array representation.
The figures show computer memory. An array uses a contiguous chunk of memory.
Linked Representation pointer (or link) in e is null c a e d b
use a variable first to get to the first element a first
Normal Way To Draw A Linked List link or pointer field of node data field of node a b c d e null first
The Class Chain
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.
Node Representation
ChainNodes:
The Class Chain link (datatype ChainNode) data (datatype T) Use ChainNode a b c d e null first length = number of elements
The Class Chain
Constructors To initialize the Chain
Chain ( ) { first = 0;}
Chain first 0 0
Chain() could also be defined as {} rather than this(0). The advantage of using this(0) is that if we later decide to add other capabilities to the constructor, these additions will need to be made in Chain(int initialCapacity) alone.
Destructor
The Method IsEmpty
The Method length()
The Method Find
The Method Search a b c d e null first
Deleting An Element Delete the first element:
Delete(1, x)
x = first −>data;
first = first−>link;
a b c d e null first
Delete(k, x) Find k-1 node and change its pointer.
p = q −>link;
q−>link = p −> link ;
x = p −>data ;
q p a b c d e null first
Delete a general Element
Delete a general element (cont.)
One-Step Insert(0,’f’) a b c d e null first f y
y −>link= first;
first = y;
Comments