程序代写代做 data structure C go Java algorithm Data Structures and Algorithms

Data Structures and Algorithms
Chapter 3

Linked Lists
• A node stores an element and a link (or links).
• Nodes are connected by links.
• A link is the reference to (or the address of) a node.
• Singly linked list, doubly linked list, circularly linked list
• Link, reference, and pointer are used interchangeably.

• Need to learn
Linked Lists
– Different linked data structures
– To write code creating and manipulating linked data structures.
– To use predefined linked data structures, such as Java’s LinkedList

Singly Linked Lists
• Nodes are connected by a single link.
• Alinkpointsto(orreferences)thenextnode.
• A node has element and the reference (or pointer) to the next node.
element
next
reference (or pointer) to The next node

Singly Linked Lists
• We usually keep two references, head and tail, for a singly linked list.

Singly Linked Lists
• Addanodetotheheadofalist
newest = Node(“Adam”); newest.next = head;
head = newest;

Singly Linked Lists • Addanodetotheheadofalist
Algorithm addFirst(e)
newest = Node(e) // new node with element e newest.next = head // new node’s next is set to refer
// to current head node head = newest // new head refers to new node
size = size + 1 // list size (node count) is // incremented

Singly Linked Lists
• Addanodetothetailofalist
newest = Node(“Adam”); newest.next = null ;
tail.next = newest; tail = newest;

Singly Linked Lists
• Addanodetothetailofalist Algorithm addLast(e)
newest = Node(e) // new node with element e newest.next = null // new node’s next is set to null tail.next = newest // current tail node’s next points to
// new node
tail = newest // new tail points to new node
size = size + 1 // list size (node count) is // incremented

Singly Linked Lists
• Removing an arbitrary node: nontrivial and inefficient.
• Removing a node from the head of a list
head tail John Susan Molly Adam
null
head = head.next;

Singly Linked Lists
Algorithm removeFirst( ) if head == null
the list is empty
head = head.next // new head points to next node size = size – 1 // list size (node count) is
// decremented

Singly Linked Lists • Generic Node class in SinglyLinkedList class
private static class Node { private E element;
private Node next;
public Node(E e, Node n) {
1
2
3
4
5
6 7}
8 public E getElement() { return element; }
9 public Node getNext() { return next; }
10 public void setNext(Node n) { next = n; }
11 }
element = e; next = n;

Singly Linked Lists
• Instance variables of SinglyLinkedList class
public class SinglyLinkedList implements Cloneable
{
// nested class Node
protected Node head = null; protected Node tail = null; protected int size = 0;
// constructors and methods

Singly Linked Lists • Complete code of SinglyLinkedList.java

Circularly Linked Lists
• A singly linked list where the last element is connect to the first element, forming a circle.
• Used in application where objects are manipulated in a round-robin manner, such as process scheduling.
• Don’t need to keep the head reference.

Circularly Linked Lists • Round-robin process scheduling: Processes are
executed by CPU one at a time for a slice of time.
// C is a circularly linked list Give a time slice to C.first() C.rotate()

Circularly Linked Lists • Rotate operation
(head)
(head)
public void rotate() { list
// rotate the first element to the back of the
}
tail BB
A tail C A C DD
Before rotation
After rotation
if (tail != null)
tail = tail.getNext();
// if empty, do nothing
// the old head becomes the new tail

Circularly Linked Lists
• Add a node to before head (this is the same as adding a node after tail)
(head)
B (head) B
A tail C A tail C
DD X
Before insertion
After insertion

Circularly Linked Lists • Can reuse most of SinglyLinkedList code.
• The addFirst method is modified
public void addFirst(E e) { // adds element e to the front of the list
if (size == 0) {
tail = new Node<>(e, null);
tail.setNext(tail); // link to itself circularly
} else {
Node newest = new Node<>(e, tail.getNext()); tail.setNext(newest);
}
size++; }

Doubly Linked Lists
• Singly linked list:
– Not easy to insert a node at an arbitrary position.
– Nontrivial to delete a node from an arbitrary position.
• These operations, however, can be performed relatively efficiently with doubly linked lists.

Doubly Linked Lists
• A node has two pointers.
• previous points to the previous node. • next points to the next node.
previous element next

Doubly Linked Lists • Doubly linked list example
header next next next
next trailer previo us
• An empty list
ABC
previo us previo us previo us
h e a d e r n e x t t ra i l e r p r e v io u s

Doubly Linked Lists
• Insert a new node X between B and C
header
X ABC
trailer
• The previous reference of X are set to point to B.
• The next reference of X are set to point to C.
header
trailer
ABXC

Doubly Linked Lists
• The next reference of B and the previous reference of C are updated to point to X.
header
trailer
ABXC
1 private void addBetween(E e, Node predecessor, Node successor) {
2 Node newest = new Node<>(e, predecessor, successor);
3 predecessor.setNext(newest);
4 successor.setPrev(newest);
5 size++;
6}

Doubly Linked Lists • Delete X
header
trailer
ABXC
• Set the next reference of B to point to C
• Set the previous reference of C to point to B.
header
trailer
ABXC

Doubly Linked Lists
• X is not a part of the list any more. The updated list is:
header
trailer
ABC
1 private E remove(Node node) {
2
3
4
5
6
7 8}
Node predecessor = node.getPrev(); Node successor = node.getNext(); predecessor.setNext(successor); successor.setPrev(predecessor);
size–;
return node.getElement();

Doubly Linked Lists • A complete code of DoublyLinkedList.java

Insertion Sort
• There are different sorting algorithms.
• Will discuss insertion sort algorithm (on an array). • Pseudocode
Algorithm InsertionSort(A)
Input: Array A of n comparable elements Output: Array A with elements rearranged in
nondecreasing order for k from 1 to n – 1do
Insert A[k] at its proper location within A[0 .. k]

• Illustration
k=2
6 17 12 32 24 8 14 11 01234567
k=6
6 8 12 17 24 32 14 11
k=3
6 12 17 32 24 8 14 11
k=7 6 8 12 14 17 24 32 11
01234567
01234567
k=4
6 12 17 32 24 8 14 11
6 8 11 12 14 17 24 32
Insertion Sort
k=1 k=5
17 6 12 32 24 8 14 11
6 12 17 24 32 8 14 11
01234567
01234567
01234567 01234567
01234567

Insertion Sort • Java implementation
1
2
3
4
5
6
7
8
9
10 11 12 13 }
public class InsertionSort {
public static void insertionSort(char[] data) {
int n = data.length;
for (int k = 1; k < n; k++) { // begin with second element // save data[k] in cur char cur = data[k]; int j = k; while (j > 0 && data[j-1] > cur) { // thus, data[j-1] must go after cur
data[j] = data[j-1]; j–;
// shift data[j-1] rightward
// and consider previous j for cur
} // while
data[j] = cur; } // for
// this is the proper place for cur // running time: O(n2)
// find correct index j for cur

Insertion Sort
• Illustration of while loop in Java implementation

Testing Equality
• When comparing two reference variables, there are two notions of equivalence.
• First interpretation: Test whether two reference variables are pointing to the same object.
• Second interpretation: Test whether the contents of the two objects pointed to by the references are the same.
String s1 = new String(“data structure”); String s2 = new String(“data structure”);
• Is s1 equal to s2?
– No, by the first interpretation
– Yes, by the second interpretation

Testing Equality
• In Java, you can compare with “==“ operator or using the
equals method.
• “==“ compares the values of the reference variables, i.e.,
it checks whether they refer to the same object.
• The equals method is defined in the Object class, and, as it is, it is effectively the same as “==“ operator.
• To implement the “second interpretation” for objects of a class, the class must define its own equals method tailored for the objects of that class.

Testing Equality
• String class has equals method which performs character-by-character, pair-wise comparison.
1 public class StringTest {
2 public static void main(String[] args) {
3
4
5
6
7
8
10 } 11 }
String s1 = new String(“data structure”);
String s2 = s1;
String s3 = new String(“data structure”); System.out.println(“reference s1 equals reference s2: ” + (s1 == s2)); System.out.println(“reference s1 equals reference s3: ” + (s1 == s3)); System.out.println(“string s1 equals string s3: ” + s1.equals(s3));
• Output: true, false, true

Testing Equality
• Equivalence testing with arrays
– a==b:Testsifaandbrefertothesamearray instance.
– a.equals(b): This is identical to a == b.
– Arrays.equals(a, b): Returns true if the arrays have the same number of elements and all pairs of corresponding elements are equal to each other. If elements are primitives, == operator is used. If elements are reference types, then a[k].equals(b[k]) is used.

Testing Equality
• Equivalence testing with linked lists
– Traverse two lists and compare pairs of corresponding elements.
– Refer to the equals method in the SinglyLinkedList class.

Cloning Data Structures • Shallow copy vs. deep copy
Shallow copy
Deep copy
Mouse
Manufacturer
price = 50 manufacturer
name = Ace
phone = (123)4567
Mouse (copy)
Manufacturer
price = 50 manufacturer
name = Ace
phone = (123)4567

Cloning Data Structures
• Java’s Object class has the clone method.
• This clone method creates a shallow copy.
• If necessary, each class must define its own clone method.

Cloning Data Structures
• Cloning arrays with elements of primitive type
int[ ] data = {1,3,5,7,9}; int[ ] backup;
backup = data;
backup = data.clone();

Cloning Data Structures
• Cloning arrays with elements of object type guests = contacts.clone( ); // a shallow copy is created
contacts
guests
Person objects

Cloning Data Structures
• Cloning arrays with elements of object type – The following is a deep copy.
– A separate code must be written.

Cloning Data Structures
• Cloning linked lists:
– Must copy one node at a time.
– Refer to the clone method in SinglyLinkedList class.

References
• M.T. Goodrich, R. Tamassia, and M.H. Goldwasser, “Data Structures and Algorithms in Java,” Sixth Edition, Wiley, 2014.