Doubly-Linked Lists

Doubly-Linked Lists

15-121 Fall 2020 Margaret Reid-Miller

Today

? Exam 1: mean 86, high 98 Amazing!!

? Hw6 will be posted tonight ? Change Hw due dates?

Plan for Today ? Singly-linked list removed at index method ? Java's LinkedList class ? Doubly-linked lists

Fall 2020

15-121 (Reid-Miller)

2

Singly-linked list

? Add at index 3 ? Insert node between nodes at index 2 and 3. ? Think add "after 2," not "before 3," as you can always add AFTER a node. ? When do you need to consider a special case? When you add the first node (after head).

? Remove at index 3 ? Remove returns the value of the node removed. ? Like add, need to remove the node "after 2" ? Are there any special cases to consider?

Fall 2020

15-121 (Reid-Miller)

3

Exercise: Remove at given index

// Removes the object at the given index. // Returns the object removed

public E remove(int index) { if (index < 0 || index > size()) throw new IndexOutOfBoundsException();

Fall 2020

15-121 (Reid-Miller)

4

Remove at index 3 goal

first

null

2

remove here

obj

(index = 3)

Fall 2020

15-121 (Reid-Miller)

5

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download