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 Node
public Node(E e, Node
1
2
3
4
5
6 7}
8 public E getElement() { return element; }
9 public Node
10 public void setNext(Node
11 }
element = e; next = n;
Singly Linked Lists
• Instance variables of SinglyLinkedList class
public class SinglyLinkedList
{
// nested class Node
protected Node
// 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
}
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
2 Node
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
2
3
4
5
6
7 8}
Node
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.