Unit02B

1

Lists

Organizing Data Linearly

Linked Lists

2B

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

2

Disadvantages of Array Lists

  If a data entry is added to or removed from an

array-based list, data needs to be shifted to

update the list.

  In the worst case, for an array-based list with n

data entries, an add and a remove takes O(n)

time.

  Also, all data in the array-based list must be

stored sequentially in memory. Large lists will

require significant contiguous blocks of memory.!

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

2

3

Singly Linked Lists

  Each data entry is stored in its own node.

  Each node has a reference to the node that

contains the next data entry.

  A reference named the head points to the node

with the first data entry.

  The last node in the list contains a reference of

null since it does not point to any other data.

  An empty list would have a head reference

equal to null.

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

4

Visualization

null

head

a data element

(type E)

a node

data next

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

3

5

Inner classes

  Since a node is specific to a linked list, we will

define the Node class to be an inner class of

the SinglyLinkedList class.

  The inner class is only accessible by the class

that enclosed it.

  Fields defined in the inner class are accessible

by its enclosing class. (No accessors are

needed.)

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

6

Node class

private static class Node<E> {

private E data;

private Node<E> next;

private Node(E element) {

data = element;

next = null;

}

private Node(E element, Node<E> nodeRef) {

data = element;

next = nodeRef;

}

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

4

7

Initializing an empty linked list

public class SinglyLinkedList<E> {

private Node<E> head;

private int numElements;

public SinglyLinkedList() {

head = null;

numElements = 0;

}

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

8

Add new first list element

Get size of list

public void addFirst(E element) {

head = new Node<E>(element, head);

numElements++;

}

public int size() {

return numElements;

}

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

5

9

Removing the first node

public E removeFirst() {

if (head == null)

throw new NoSuchElementException();

E result = head.data;

head = head.next;

numElements--;

return result;

}

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

10

Traversing the list

!public String toString() {

String result = "";

Node<E> nodeRef = head;

while (nodeRef != null) {

result += nodeRef.data + " ==> ";

nodeRef = nodeRef.next;

}

return result;

}

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

6

11

Add at given index

public void add(int index, E element) {

if (index < 0 || index > size())

throw new

IndexOutOfBoundsException();

if (index == 0) {

addFirst(element);

return;

}

// cont'd

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

12

Add at given index

Visualization

null

head

null

newNode

nodeRef

insert here

(index = 3)

WRONG

1

2

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

7

13

Add at given index

Visualization

null

head

null

newNode

nodeRef

insert here

(index = 3)

RIGHT

1

2

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

14

Add at given index

(cont'd)

Node<E> newNode

= new Node<E>(element);

Node<E> nodeRef = head;

for (int i = 1; ______________; i++)

nodeRef = nodeRef.next;

newNode.next = nodeRef.next;

nodeRef.next = newNode;

numElements++;

}

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

8

15

Remove at given index

!public E remove(int index) {

if (index < 0 || index >= size())

throw new IndexOutOfBoundsException();

if (index == 0) {

return removeFirst();

}

// cont'd

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

16

Remove at given index

Visualization

null

head nodeRef

remove here

(index = 3)

WRONG

1

result

2

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

9

17

Remove at given index

Visualization

null

head nodeRef

remove here

(index = 3)

RIGHT

2

result

1

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

18

Remove at given index

(cont'd)

Node<E> nodeRef = head;

for (int i = 1; ______________; i++)

nodeRef = nodeRef.next;

E result = nodeRef.next.data;

nodeRef.next = nodeRef.next.next;

numElements--;

return result;

}

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

10

19

Complexity

On a singly linked list with n nodes:

addFirst _______________

removeFirst _______________

add _______________

remove _______________

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

20

Disadvantages of Singly

Linked Lists

  Insertion into a list is generally linear.

  In order to insert a node at an index greater

than 0, we need a reference to the previous

node.

  In order to remove a node that is not the first

node, we need a reference to the previous

node.

  We can only traverse the list in one direction.

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

11

21

Doubly-Linked Lists

  Each data entry is stored in its own node.

  Each node has a reference to the node that contains the

next data entry and a reference to the node that contains

the previous data entry (prev).

  A reference named the head points to the node with the

first data entry and a reference named the tail points to

the node with the last data entry.

  The last node in the list contains a next reference of null

and the first node in the list contains a prev reference of

null.

  An empty list would have head and tail references equal

to null.!

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

22

Doubly-Linked Lists

null null

NOTE: Data is not shown.

head

tail

prev data next

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

12

23

Inserting into

Doubly-Linked Lists (1)

null null

NOTE: Data is not shown.

head

tail

newNode

nodeRef

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

24

Inserting into

Doubly-Linked Lists (2)

null null

NOTE: Data is not shown.

head

tail

newNode

nodeRef

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

13

25

Inserting into

Doubly-Linked Lists (3)

null null

NOTE: Data is not shown.

head

tail

newNode

nodeRef

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

26

Inserting into

Doubly-Linked Lists (4)

null null

NOTE: Data is not shown.

head

tail

newNode

nodeRef

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

14

27

Inserting into

Doubly-Linked Lists (5)

null null

NOTE: Data is not shown.

head

tail

newNode

nodeRef

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

28

Inserting into

Doubly-Linked Lists

null null

NOTE: Data is not shown.

head

tail

nodeRef

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

15

29

Inserting into

Doubly-Linked Lists

null null

NOTE: Data is not shown.

head

tail

How would you implement addFirst?

How would you implement addLast?

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

30

Removing from

Doubly-Linked Lists

null null

NOTE: Data is not shown.

head

tail

nodeRef

How would you remove the node referenced by nodeRef?

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

16

31

Removing from

Doubly-Linked Lists

NOTE: Data is not shown.

null

head tail

nodeRef

What if head = tail?

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

32

Removing from

Doubly-Linked Lists

NOTE: Data is not shown.

What if nodeRef = head?

null null

head

tail nodeRef

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA

17

33

Removing from

Doubly-Linked Lists

NOTE: Data is not shown.

What if nodeRef = tail?

null null

head

tail

nodeRef

15-121 Introduction to Data Structures, Carnegie Mellon University - CORTINA