程序代写代做 chain C data structure Linked List and Queue

Linked List and Queue
Daniel Archambault
CS-115: Linked List and Queue
1

Previously in CS-115
class Playable
private double dur;
public void play ();
class DVD
private String director;
public void play ();
Inheritance and Generics
class CD
private String artist;
CS-115: Linked List and Queue
2

Previously in CS-115
What is the main advantage of using a generic?
CS-115: Linked List and Queue
3

Previously in CS-115
What is the main advantage of using a generic? What is a type parameter?
CS-115: Linked List and Queue
3

Previously in CS-115
What is the main advantage of using a generic? What is a type parameter?
Can we use simple types as a type parameter?
CS-115: Linked List and Queue
3

Previously in CS-115
What is the main advantage of using a generic? What is a type parameter?
Can we use simple types as a type parameter? IsT t = new T();valid?
CS-115: Linked List and Queue
3

Previously in CS-115
What is the main advantage of using a generic? What is a type parameter?
Can we use simple types as a type parameter? IsT t = new T();valid?
Can we have type parameters on specific methods?
CS-115: Linked List and Queue
3

Previously in CS-115
It’s time to build towards data structures
Linked Lists and Queue
CS-115: Linked List and Queue
4

List ADT
Types of operations on data, typically:
􏰀 Add data to the list
􏰀 Remove elements from the list
􏰀 Query the list
Can use an array for this but a linked list has advantages
CS-115: Linked List and Queue
5

Link List as a Chain…
Links are nodes
􏰀 a reference to the rest of the chain (join links)
􏰀 a value at the current link
Think of a chain with a direction Alternative to an array
CS-115: Linked List and Queue
6

Linked List Data Structure
tail
public class Link {
private Link next;
private Object element; }
public class LinkedList {
private Link head;
private Link tail; }
head
null
next element
Obj.
next element
next element
Obj.
Obj.
CS-115: Linked List and Queue
7

Linked List Navigation
Navigation is entirely based on references
Indexes have less meaning
Objects in list only make sense in terms of relative position
CS-115: Linked List and Queue
8

How do we look something up?
public class LinkedList { …
public Object getItem (int index) {
Link curItem = head;
for (int i = 0; i < index; ++i) { curItem = curItem.next; } return curItem.element; } ... } Follow the chain from the head! We are slower than an array for random access 􏰀 What do we do in the array case? CS-115: Linked List and Queue 9 Where are link lists useful? We are slower for lookups in the general case However, we are better for inserts and deletes Why? 􏰀 the position of an element only depends on its neighbours 􏰀 the position is not absolute 􏰀 the size of the list is not absolute CS-115: Linked List and Queue 10 Insertion in Linked List head Obj. prev temp tail next element next element next element null newNode Obj. Obj. next element ... //prev is the reference before and next is the reference after Link temp = prev.next; prev.next = newNode; newNode.next = temp; ... Once have position, insertion is low cost Array implementation? Must move everyone over Obj. CS-115: Linked List and Queue 11 Deletion in Linked List prev temp tail next element next element next element head null Obj. ... //prev is the node before and next is the node after Link temp = prev.next; prev.next = temp.next; ... Once have the position, deletion is low cost Array implementation? 􏰀 What happens when the list gets small? Obj. Obj. CS-115: Linked List and Queue 12 Advantages/Disadvantages Linked list advantage/disadvantage 􏰀 slower accesses in the general case 􏰀 cheap insertion/deletion in the general case 􏰀 store only what we need Array advantage/disadvantage 􏰀 fast accesses in the general case 􏰀 slower insertion or deletion in the general case 􏰀 sometimes require more storage than we need CS-115: Linked List and Queue 13 Queue ADT First in first out public interface Queue { public boolean isEmpty (); public void enqueue (Object newItem); public void dequeue (); public Object peek (); } CS-115: Linked List and Queue 14 isEmpty behaviour Returns true if there are no elements in the queue Otherwise, returns false (a) true d b e f c (b) false CS-115: Linked List and Queue 15 enqueue behaviour Adds an item to the back of the queue d b e f c (c) before enqueue of w d b e f c w (d) after enqueue CS-115: Linked List and Queue 16 dequeue behaviour Removes an item from the front of the queue d b e f c (e) before dequeue d b e f c (f) after dequeue CS-115: Linked List and Queue 17 peek behaviour Returns the front of the queue d b e f c (g) returns d CS-115: Linked List and Queue 18 Implementation of Queue To turn a ADT Queue into a Queue data structure we can choose either an array or linked list 􏰀 most natural implementation is linked list I’ll explain this implementation with a linked list CS-115: Linked List and Queue 19 Attributes of Queue Implemented with Linked List public class Queue { private Link head; private Link tail; public Queue () { head = null; tail = null; } } CS-115: Linked List and Queue 20 isEmpty implementation Simply check if the queue is empty Really, could just check head, but this prevents bugs ... return ((head == null) && (tail == null)); ... CS-115: Linked List and Queue 21 enqueue implementation Adds an item to the back of the queue Simply move tail back one If tail is null, you need to set head and tail... ... Link newNode = new Link (element, null); tail.next = newNode; tail = newNode; ... CS-115: Linked List and Queue 22 dequeue implementation Removes an item from the front of the queue Simply remove the link in front ... head = head.next; ... Check if head is null. If so, set tail null (queue empty). CS-115: Linked List and Queue 23 peek implementation Returns the front of the queue If the queue is empty, you need to throw an exception ... return head.element; ... CS-115: Linked List and Queue 24