Transcript linked list

COP 3540 Data Structures with OOP
Chapter 5 - Part 2
Linked Lists
Abstract Data Types and Sorted Lists
1/26
Abstract Data Types
 A wonderful way to deal with data
structures.
 An ADT is a way of looking at a data
structure focusing on what it does and NOT
how it does whatever it is supposed to do.
 We implement an ADT
 Stacks and Queues are examples of ADTs.
 They are ‘concepts’ ; logical data structures.
 Let’s first look how we can have a linked list
that implements a stack.
2/26
A Stack Implemented by a Linked List
 Can use an array, but no chance to extend it.
 Basic operations: push() and pop() implemented as
 arr[++top] = newdata; and returnedData = arr[top--];
 Indexes are checked for stack overflow and stack underflow
and then adjusted as shown.
 For a Stack: implemented as a linked list, we have
 theList.insertFirst(data) to add an element onto the stack
• (looks like a ‘push’)
 Retrieved data = theList.deleteFirst(). (looks like a pop)
  The important things: user calls push() and pop()
for his/her stack operations and has no knowledge
whether the logical stack is implemented as a physical
array or as a physical linked list!
3/26
Client Application
class LinkStackApp
{
public static void main(String[] args)
{
LinkStack theStack = new LinkStack(); // makes one stack object
// We know nothing about the stack’s implementation from declaration.
theStack.push(20);
theStack.push(40);
// push items
theStack.displayStack();
// display stack
theStack.push(60);
theStack.push(80);
// push items
theStack.displayStack();
// display stack
theStack.pop();
theStack.pop();
// pop items
theStack.displayStack();
} // end main()
} // end class LinkStackApp
All generic at this point; abstract!
// display stack
all standard stack operations!!
4/26
No Changes here…just the nodes…
class Link (objects of this class are the nodes themselves!)
{
public long dData;
// data item
public Link next;
// next link in list; note: single link.
// ------------------------------------------------------------public Link(long dd)
// constructor
{ dData = dd; }
// ------------------------------------------------------------public void displayLink()
// display ourself
{ System.out.print(dData + " "); }
} // end class Link
// Note: this is really only the data (and the link) and not
the most important methods…
5/26
class LinkStack
{
private LinkList theList; ===============================
//-------------------------------------------------------------public LinkStack()
// constructor
{
theList = new LinkList();
}
//-------------------------------------------------------------public void push(long j) // put item on top of stack
{
theList.insertFirst(j);
}
//-------------------------------------------------------------public long pop()
// take item from top of stack
{
return theList.deleteFirst();
}
//-------------------------------------------------------------public boolean isEmpty()
// true if stack is empty
{
return ( theList.isEmpty() );
}
//-------------------------------------------------------------public void displayStack()
{
System.out.print("Stack (top-->bottom): ");
theList.displayList();
}
//-------------------------------------------------------------6/26
} // end class LinkStack
Client made an object of
this class.
This is the Interface to the
implementation
Can see a generic ‘push’
and ‘pop’ etc….
User sees the headers;
not the implementation.
See some implementation
via the constructor where
a linked list is created.
class LinkList
{
private Link first;
Here’s the linked list implementation!
// ref to first item on list
Here is your control class for the Linked List –
your ‘collection class,’ if you will”
Note the methods and what they operate on!!
public LinkList()
// constructor
{ first = null; }
// no items on list yet
public boolean isEmpty()
// true if list is empty
{ return (first==null); }
public void insertFirst(long dd) // insert at start of list
{
// make new link
Link newLink = new Link(dd);
newLink.next = first;
// newLink --> old first
first = newLink;
// first --> newLink //can you draw these steps???
}
public long deleteFirst()
// delete first item
insertion part
{
// (assumes list not empty)
deletion part too
Link temp = first;
// save reference to link
first = first.next;
// delete it: first-->old next
return temp.dData;
// return deleted link //can you draw these steps???
}
public void displayList()
{
Link current = first;
// start at beginning of list
while(current != null)
// until end of list,
Note: the push is implemented via insertFirst()
The pop is implemented via deleteFirst().
{
which are linked list operations.
current.displayLink(); // print data
current = current.next; // move to next link
Logical operations implemented on physical structures
}
System.out.println("");
} // end class LinkList
7/26
Discussion of Stack implemented with a Linked List
 In the LinkStackApp, we pushed two items
onto the stack
 Displayed the stack
 Pushed two more items
 Displayed stack again
 Popped two items
 Displayed the remaining stack.
 Design: LinkStackApp  LinkStack 
LinkList  Link.
 Beautiful part: When client calls push() or
pop(), generic stack operations, s/he has no
idea HOW the stack is implemented!!
8/26
A Queue Implemented by a Linked List
 Same song, second verse.
 Idea is to have operations
 insert() and
 remove() (both logical queue operations…)
 that are meaningful to the client but yet do
NOT reveal the design and implementation
of those operations.
 Consider the following Java code:
9/26
Client
class LinkQueueApp (our Main)
{
public static void main(String[] args)
{
LinkQueue theQueue = new LinkQueue();
Application
// Could be used to create a number of queues!
// We know nothing about the queue’s implementation
theQueue.insert(20);
theQueue.insert(40);
// insert items
theQueue.displayQueue();
theQueue.insert(60);
theQueue.insert(80);
// display queue
// insert items
theQueue.displayQueue();
// display queue
theQueue.remove();
theQueue.remove();
theQueue.displayQueue();
} // end main()
} // end class LinkQueueApp
// remove items
// display queue
10/26
// Here are our queue items…(nodes here) No changes here!
(simply the nodes themselves)
These are ‘entity’ classes; data classes; objects;
class Link { //this is our queue data and stack data items suitably
modified with two links for a queue object and one link for stack
object. In program2, design one class called Queue and a second:
Stack. (two links because we are building a doubly-linked list for
the queues)
public long dData;
// data item
public Link next;
// next link in list
// ------------------------------------------------------------public Link(long d)
// constructor
{ dData = d; }
// ------------------------------------------------------------public void displayLink()
// display this link
{ System.out.print(dData + " "); }
// ------------------------------------------------------------11/26
} // end class Link
Here’s the Interface to the implementation
class LinkQueue
{
This app made an object of this.
private FirstLastList theList;
This is interface to implementation:
//-------------------------------------------------------------public LinkQueue()
// constructor
Collection Class; Driver….
{
LL_Control class. You will need
theList = new FirstLastList();
} // end constructor; make a 2-ended list
one object of this type per queue (4)
//-------------------------------------------------------------public boolean isEmpty()
// true if queue is empty
{
return theList.isEmpty();
}// end IsEmpty()
//-------------------------------------------------------------public void insert(long j)
// insert, rear of queue
{
theList.insertLast(j);
See logical operation:
}// end insert()
insert().
//-------------------------------------------------------------See the implementation
public long remove()
// remove, front of queue
which is insertLast().
{
return theList.deleteFirst();
}// end remove()
Queue goes right to left.
//-------------------------------------------------------------Rear of queue is on right
public void displayQueue()
Front of queue is on left.
{
Insert() in rear (right)
System.out.print("Queue (front-->rear): ");
Remove() from front (left)
theList.displayList();
See drawings ahead…
12/26
}// end displayQueue()
class FirstLastList {
private Link first;
// reference to a Link - first item
private Link last;
// reference to a Link - last item
public FirstLastList() {
// constructor
// no items on list yet
starting off values: first = null;
last = null;
// sets these reference values to null.
}
public boolean isEmpty()
// true if no links



Here is the implementation
Here’s your queue.
{ return first==null; }
public void insertLast(long dd) {
// insert at end of list (rear)
Link newLink = new Link(dd); // make new link  creates object!!
if( isEmpty() )
// if empty list,
first = newLink;
// first --> newLink
else
last.next = newLink;
// old last --> newLink
last = newLink;
// newLink <-- last // adjusts rear where new node is added.
Here’s the implementation!
}
Queue implemented via a
public long deleteFirst() { // delete first link
Linked List.
long temp = first.dData; // (assumes non-empty list)
if(first.next == null)
// if only one item
last = null;
// null <-- last
first = first.next;
// first --> old next
// adjusting new front as node is removed.
return temp;
}
public void displayList() {
Link current = first;
// start at beginning
while(current != null)
// until end of list,
{
current.displayLink();
// print data
13/26
current = current.next; // move to next link
First = null
Initially:
Last = null
First = newLink
Add first link:
123
null
Last = newLink
Link newLink = new Link(dd);
// make new link  creates object!!
newlink
123
Add next link:
newLink
334
null
last.next = newLink;
null
last.= newLink;
last
newlink
123
newLink
334
Front of Queue
last
Note: insert() is into the rear of the queue.
(This can be implemented either way: where the
‘rear’ is on the left…)
14/26
Discussion of Queues Implemented via Linked Lists
 Again, merely implementing a queue using a linked
list data structure instead of an array.
 Note that linkStack and linkQueue

stacks and queues are conceptual entities.
 They are the interfaces to the real implementations.
 Their implementations represent the physical
realization of these conceptual entities.
 Choice? Array or Linked List?
 Speed is about the same.
 Uncertain size  use linked list
 (linked list is also more complex…)
15/26
Data Types and Abstraction
 Abstract Data Types.
 Primitives types: data with certain characteristics and sets of
operations that can be performed on that data.
 In the computer, there are bounds too on primitive data types due to
the computer’s architecture. (231 -1 for positive ints; -231 for neg ints)
 User-defined data types (quantitative types)
• Some can represent numerical goodies consisting of primitive data
types. (Complex numbers? (2+3i ) Rational numbers? 1/3)
Operations must be specified. (no division by zero, etc.)
• Can/Must define their attributes and their operations
 User-defined data types (non-quantitative types)
• Consists of user-defined data types / combinations and the userdefined operations permissible on them, like getCountry(), etc...
 Data types are defined to hold certain arrangements of data and
possess sets of operations acceptable/appropriate to the data.
16/26
Data Types and Abstraction
 “Abstract”  the data description is considered apart from
whatever implementation might be used to deal with it.
 Classes are abstractions – apart from the individual objects.
 In OOP, we have lots of ADTs. (Think stacks, queues, trees…)
 Have descriptions of fields and methods
 Contain NO details regarding these implementations.
• These are done on purpose to provide uniform interfaces (like
push() and pop() and insert()… yet provide opportunity for specific
implementations that are more appropriate is some instances.
 A client has access to the methods (through the method interface) and
how to invoke, and what to expect in return. (public void push (int i) )
 A client is NOT shown how the methods are implemented.
 Another example: in String objects, we do not know how ‘compareTo’
is actually implemented. We do know how it works, how to use it, and
what to expect in return.
17/26
ADTs as a Design Tool
( Think country classes…)
 Consider what it is you need to do with data.
 Operations. What operations need to be performed on the
data?
 Access: How do you need to access it?
 Do you need to access an element via key? in specific sorted order?
First one in a list, last one in a list?
 THEN decide on the ADT, whose definition is determined by
the operations you need to perform on the data.
 Decouple the specification of ADT from implementation.
  Can change the implementation later!
  This is its beauty! Can always improve implementation.
 Naturally the underlying data structure must make the
specified operations as efficient as possible.
 Need sequential access? Perhaps a linked list.
 Need random access? A linked list does not provide this.
An array does if you know the index of the desired array
element. Array can be sorted easily too.
18/26
Example of a Subsystem (Architectural Design)
 Subsystem: Maintain Credit Profile Subsystem
 Desired Operations:





Create New Profile
Change Profile
Delete Profile
Get Profile
Display Profile, ….
Maintain Credit Profile Subsystem
(subsystem realizes the interface)
MCPS - Int
<< interface >>
Create_profile();
Change_profile();
Delete_profile();
Get_profile();
Display_profile();
These are the operations needed. Provided in interface.
In a subsystem, implementation is provided inside subsystem,
19/26
whose contents is not available to client. Interface, however, is.
With lots of connections / dependencies, etc.
SORTED Linked LISTS
 Lists where items are in an order.
 Sorted on some key value usually inside the node.
 Can delete via a find() followed by a ‘logical’ delete()
 Can have sorted list in same way as a sorted array.
 Advantages of a sorted linked list over a sorted array
 are those deficiencies found in the processing of arrays:
 Speed of insertion: ( O(n) )
• Find place for new item (‘same’ search time as array)
 But to Insert in linked list: other items don’t need to be moved!!!)
 Size of list
• the fact that the size of the list can expand almost
indefinitely.
 Disadvantage: Cannot do a binary search on a sorted
linked list.
20/26
Java Code to Insert an item into a Sorted List
Clearly, there must be a search algorithm to
find the place where the new item should go.
insert() routine is in book. (will look at this ahead…)
Essentially it is a search routine to find the place to
insert the new list item.
Remember: when searching (with a goal of inserting
or deleting) a singly-linked list, you MUST keep
the location (reference) of ‘previous’ link when
looking at a ‘current link.’
Not true for a doubly linked list next set of slides.
21/26
Additional Considerations
 When inserting into a sorted list, new entry may
well be placed logically somewhere within the
list. Physically? We don’t know / care where…
 Boundary Conditions:
 But it may be the new ‘first’ element in the list.
 Could also be ‘last’
 Error Conditions:
 May also be a duplicate!! (generally not wanted)
 May not be able to find link if we are to ‘change’
 Let’s look at the unique code:
22/26
class SortedList {
private Link first;
// ref to first item
public SortedList()
// constructor
{ first = null; }
public boolean isEmpty()
// true if no links
{ return (first==null); }
public void insert(long key) { // insert, in order
Link newLink = new Link(key); // make new link
Link previous = null;
// start at first
Link current = first;
while(current != null && key > current.dData) {
// or key > current,
previous = current;
// note: sort is ‘descending’
current = current.next;
// go to next item
} // end while
if(previous==null)
// at beginning of list
first = newLink;
// first --> newLink
else
// not at beginning
{
previous.next = newLink;
// old prev --> newLink
newLink.next = current;
// newLink --> old currnt
} // end else
} // end insert()
public Link remove() { // return & delete first link
// (assumes non-empty list)
Link temp = first;
// save first
first = first.next;
// delete first
return temp;
// return value
}
public void displayList() {
System.out.print("List (first-->last): ");
Link current = first;
// start at beginning of list
while(current != null) { // until end of list,
current.displayLink(); // print data
current = current.next; // move to next link
}
23/26
System.out.println("");
code. Of interest.
Must find the right spot!!
Efficiency of Sorted Linked Lists
 Inserting and deleting any item in a sorted linked list
requires O(n) comparisons (that is a number of
comparisons directly proportional to the number of
items IN the list) with n/2 being the average.
 The smallest (minimum item) can be found or deleted
in O(1) time since it is in the beginning of the list. (or
end of the list if you maintain ‘first’ and ‘last’ pointers.)
  If access is frequently in the beginning, this is
good and if inserting is not done a lot or the speed is
not critical, sorted linked lists are pretty effective.
 Using the notion of a sorted list, realize that a priority
queue might be implemented by a sorted linked list.
24/26