Data Structures

<Lecture 6: List 2>

Sungmin Cha
New York University

09.23.2024
 Outline
• Notice

• Review the previous lecture

• List
– LinkedList
– Doubly Linked List
– Collection Framework

2
 Outline
• Notice

• Review the previous lecture

• List
– LinkedList
– Doubly Linked List
– Collection Framework

3
 Submission to Gradescope (HW1 P3)

• Make the ‘customlist.zip’ file and submit it!

– Case 1: making the compressed file with individual files

 Causes an error in Gradescope!

– Case 2: compressing the ‘customlist’ directory directly

4 / 19
 Notice
• HW1
– Part 1
 Calculate the time complexity of a code (2-3 problems)
– Part 2
 Solve the problem using a recursive function (1 problem)
– Part 3
 Implement ArrayList, LinkedList

– Deadline: 10.06.2024
– Submit to Gradescope (individually, no group work)
 However, the discussion in Ed is allowed

5
 Outline
• Notice

• Review the previous lecture

• List
– LinkedList
– Doubly Linked List
– Collection Framework

6
 ADT
• From ADT to the user program
1. Designing ADT
2. Designing JAVA Interface
3. Implementing Class
4. User program

7
 ADT of Array List
• Designing ADT for Array List

– We consider that 10 operations should be implemented to

manage an array as a list

8
 Array List
• Advantages and disadvantages of Array List
– Advantages
1. Simple to implement
2. Data referencing is convenient: it allows quick access anywhere based
on the index value

– Disadvantages
1. The length of the array must be determined initially; if it needs to be
changed, a new allocation of the array is necessary
2. During the process of adding or deleting data, frequent data
movement (copying) occurs

9
 Outline
• Notice

• Review the previous lecture

• List
– ArrayList
– Abstracted Data Type (ADT)
– Operations

10
 From Array List to Linked List
• Problem of Array List
– It has a statically determined size for the array
– If we declare an array with more than enough size
 It results in wasteful use of space
– If we set a small size of the array
 When the array becomes full, we have to reallocate a larger array
 Also, we have to transfer all the data to it (high cost)

– In other words, a static array cannot adapt flexibly to the

required memory size.

It is possible to allocate space for the list

dynamically as elements are added?
11
 Linked List
• Basic form of Linked List null
A node refers to the next node

10 17 35 40 55 24

last node

Node configuration
head

– Empty Linked List

: head (reference) item next

null Field for referring next node

head Field for storing an element 12
 Linked List
• The memory map of Linked List
Heap memory

35
17
24

40
55

10

head

– In heap memory, each node is not allocated consecutively

– However, we can control them because each node refers to
the next node 13
 Linked List
• Designing ADT for Linked List

– Because Linked List is also a List, we can use the same ADT
 Only the difference is using an array or linked node to implement a List
– We also consider 10 operations for Linked List

14
 Linked List
• getNode(𝑘) function for Linked List
– In Array List, we can easily access the node k of an array
 Time complexity: O(1)
– Can we access the node k of the linked list directly?
 No!
 Sequential access from the head is necessary to reach the node k

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

head
15
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

head

16
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

getNode(2)

numItems = 5
node 0 node 1 node 3 node 4

10 17 35 40 55

head

17
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

1. Set a new currNode

head
currNode

18
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

2. Assign the location stored in head to currNode

head
currNode

19
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

2. Assign the location stored in head to currNode

: currNode = head
head
currNode

20
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

3. Assign currNode.next to currNode (i=0, i<k)

head
currNode

21
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

3. Assign currNode.next to currNode (i=0, i<k)

: currNode = currNode.next
head
currNode

22
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

4. Assign currNode.next to currNode (i=1, i<k)

head
currNode

23
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

4. Assign currNode.next to currNode (i=1, i<k)

: currNode = currNode.next
head
currNode

24
 Linked List
• getNode(k) function for Linked List
– A function to access the node k in a linked list
 Example: getNode(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

4. return currNode

head
currNode

25
 Linked List
• What is the time complexity of getNode(k)?
– When is the worst case?
 k == numItems
– O(n) where n = numItems

• Pseudo code of getNode(k)

26
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 1) add a node in the middle of a linked list
 Example: add(2, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

head

27
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 1) add a node in the middle of a linked list
 Example: add(2, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

1. Set a new reference prevNode

: prevNode
head
prevNode

28
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 1) add a node in the middle of a linked list
 Example: add(2, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

2. Assign getNode(k-1) to prevNode

: prevNode = getNode(k-1)
head
prevNode

29
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 1) add a node in the middle of a linked list
 Example: add(2, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

3. Allocate a new node

3 newNode.item = 3
head
prevNode

30
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 1) add a node in the middle of a linked list
 Example: add(2, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

4. Set newNode.next
3 newNode.next = prevNode.next
head
prevNode

31
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 1) add a node in the middle of a linked list
 Example: add(2, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

5. Set prevNode.next
3 prevNode.next = newNode
head
prevNode

32
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 1) add a node in the middle of a linked list
 Example: add(2, 3)

numItems = 6
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

6. numItems++
3
head

33
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 2) add a node in the beginning of a linked list
 Example: add(0, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

There is no previous node of the node 0

head we cannot use ‘prevNode’!

34
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 2) add a node in the beginning of a linked list
 Example: add(0, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

1. Allocate a new node

3 newNode.Item = x
head

35
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 2) add a node in the beginning of a linked list
 Example: add(0, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

2. Set newNode.next
3 newNode.next = head
head

36
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 1) add a node in the beginning of a linked list
 Example: add(0, 3)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

3. Set Head
3 head = newNode
head

37
 Linked List
• add(k, x) function of Linked List
– Add a new node with the value of x to the node k
– Case 1) add a node in the beginning of a linked list
 Example: add(0, 3)

numItems = 6
node 0 node 1 node 2 node 3 node 4 node 5

3 10 17 35 40 55

4. numItems++

Head

38
 Linked List
• What is the time complexity of add(k,x)?
– The time complexity of add(k,x) depends on getNode(k-1)
– The worst case: adding a node to the end of a linked list
 O(n), where n = numItems

• Pseudo code of add(k, x)

39
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 1) Remove a node in the middle of a linked list
 Example: remove(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

head

40
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 1) Remove a node in the middle of a linked list
 Example: remove(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

1. Set a new reference prevNode

: prevNode
head
prevNode

41
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 1) Remove a node in the middle of a linked list
 Example: remove(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

2. Assign getNode(k-1) to currNode

: prevNode = getNode(k-1)
head
prevNode

42
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 1) Remove a node in the middle of a linked list
 Example: remove(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

3. Set prevNode.next
head
prevNode

43
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 1) Remove a node in the middle of a linked list
 Example: remove(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

3. Set prevNode.next
head : prevNode.next prevNode.next.next
prevNode

44
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 1) Remove a node in the middle of a linked list
 Example: remove(2)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

3. Set prevNode.next
head : prevNode.next = prevNode.next.next
prevNode

45
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 1) Remove a node in the middle of a linked list
 Example: remove(2)

numItems = 4
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

4. numItems--
head

46
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 2) Remove a node in the beginning of a linked list
 Example: remove(0)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

There is no previous node of the node 0

head we cannot use ‘prevNode’!

47
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 2) Remove a node in the beginning of a linked list
 Example: remove(0)

numItems = 5
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

1. Set head
head = head.next
head

48
 Linked List
• remove(k) function of Linked List
– Remove the node k from a linked list
– Case 2) Remove a node in the beginning of a linked list
 Example: remove(0)

numItems = 4
node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

2. numItems--
Head

49
 Linked List
• What is the time complexity of remove(k)?
– The time complexity of remove(k) depends on getNode(k-1)
– The worst case: removing a node to the end of a linked list
 O(n), where n = numItems

• Pseudo code of remove(k)

50
 Linked List
• Using Dummy Head for simplicity in implementations
– Both add() and remove() have a different implementation
(such as, for k=0 and others)
– Why is the implementation for k=0 different?
 There is no previous node of the node 0

51
 Linked List
• Using Dummy Head for simplicity in implementations
– Adding Dummy Head Node at the beginning of a linked list
 Dummy head node: a fake node that doesn’t have a value
dummy head node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

Fake node The real nodes with node indices starting from 0
(index: -1)

Head dummy head

– Empty linked list
 With a dummy head node
Dummy head node is not
treated as the real node

Head 52
 Linked List
• Advantage of using Dummy Head Node
– When we add or remove a node to the middle and last of a
linked list, the approach remains the same as before
– In the case of adding or removing a node to the beginning of a
linked list
dummy head node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

Head We can set prevNode!

prevNode
53
 Linked List
• add(k,x) in the case of using Dummy head
– When we add a node to the middle and last of a linked list, the
approach remains the same as before
– In the case of adding a node to the beginning of a linked list
 Example: add(0,3)
dummy head node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

Head

prevNode
54
 Linked List
• add(k,x) in the case of using Dummy head
– When we add a node to the middle and last of a linked list, the
approach remains the same as before
– In the case of adding a node to the beginning of a linked list
 Example: add(0,3)
dummy head node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

Head

No need to separately consider

the case k=0
55
 Linked List
• remove(k) in the case of using Dummy head
– When we add a node to the middle and last of a linked list, the
approach remains the same as before
– In the case of removing a node to the beginning of a linked list
 Example: remove(0)
dummy head node 0 node 1 node 2 node 3 node 4

10 17 35 40 55

Head We can set prevNode!

prevNode
56
 Linked List
• remove(k) in the case of using Dummy head
– When we add a node to the middle and last of a linked list, the
approach remains the same as before
– In the case of removing a node to the beginning of a linked list
 Example: remove(0)
dummy head

10 17 35 40 55

Head

No need to separately consider

prevNode the case k=0
57
 Linked List
• Other operations
– set(k, x): set x to the node k
– indexOf(x): get the index of node that has x as an element
– len(): get the number of elements
– isEmpty(): check whether the linked list is empty
– clear(): Clear the linked list

58
 Linked List
• Comparing Array and Linked List
– n: the total number of elements in a list

Array List Linked List

Allocation Type Static Dynamic
Consecutive Allocation Yes No
Time Complexity of O(1) O(n)
indexing
Memory Overhead - Additional memory is
required for a link

59
 Linked List
• Comparing Array and Linked List
– Use Array List when
 Random access and retrieval of elements by index are frequent
operations
– Use Linked List when
 Frequent insertions or deletions are expected, especially in the
middle of the list

60
 Other Types of Linked List
• Doubly Linked List
– Limitation of Linked List?

dummy head

10 17 35 40 55

head

 Linked list is linked in only one direction

 Consider the scenario where we need to access nodes with values ‘55’,
‘40’, ‘35’, ‘17’ and ‘10’ sequentially.

61
 Other Types of Linked List
• Doubly Linked List
– Each node is connected to both the previous and next node

dummy head

10 35 40

head

62
 Other Types of Linked List
• Advantages and disadvantages
– Advantages
 Efficient traversal and access
: when consecutive searches are conducted, reducing search time
– Disadvantages
 Additional memory costs due to one additional variable (prev)
 Complex implementation

63
 JAVA Collection Framework
• Collection Framework

64
 JAVA Collection Framework
• Collection Framework
– Data structures are already implemented in the Collection
Framework
 They are implemented in an optimized way
– In other words, there is no need for us to implement the data
structures from scratch
 In the Lab, we will practice problem-solving using them

– To enhance our understanding of the details of each data

structure and to improve our programming skills,
 it is necessary to gain hands-on experience in implementing them!

65
 Thank you!

E-mail: sungmin.cha@nyu.edu

66