Singly-Linked List Class - Carnegie Mellon University
[Pages:48]Singly-Linked List Class
15-121 Fall 2020 Margaret Reid-Miller
Exam 1 during class Thursday
? Please email mrmiller@cs.cmu.edu if you will have any difficulties and need accommodations.
? Topics include everything except Linked Lists. ? Review Sessions:
? Sean: Today 5pm ? 6pm ? Margaret: Wednesday during lab (attendance
not required) ? Leah: Wednesday 5pm - 6pm
Fall 2020
15-121 (Reid-Miller)
2
Today
? Homework 5 problems and checkpoint: last day to submit was last night. ? Solution to problems will be posted on autolab later today.
? Today ? Implementing a generic Linked List class
Fall 2020
15-121 (Reid-Miller)
3
How to deal cards in HW5 card game.
? What are two ways to deal a card from a pile?
? pile.remove(0)
O(n)
? pile.remove(pile.size()-1) O(1)
? Which is easier to code? ? Which is the more efficient? The latter. Why?
? Never again will you get away with using remove(0) or add(0, E) if you can reframe the code to use remove and add at the end of the array list!
Fall 2020
15-121 (Reid-Miller)
5
Linked Lists
? Advantages:
? Don't need large blocks of contiguous memory.
? Breaks up an array into little pieces
? Can grow and shrink without copying data.
? Disadvantages:
? Access is sequential. Slow to access the middle of the list.
? What arrays/ArrayLists do well, linked list do poorly and vice versa.
Fall 2020
15-121 (Reid-Miller)
6
Singly-linked list visualization
data next
a node
head
list
"A"
"B"
"C"
? A reference, often called the head, points to the node with the first data entry.
? The last node in the list contains null as its reference to the next node signifies the end of the list.
? How do you create an empty linked list? Node list = null
Fall 2020
15-121 (Reid-Miller)
8
An empty linked list has a head reference equal to null.
? This is very different than Strings or ArrayLists
? If I have an empty String, ? I can still ask for its length and ? check if it is equal to another String.
? If I have an empty ArrayList, ? I can still ask for its size and ? add elements to it.
Fall 2020
15-121 (Reid-Miller)
9
What does the following Java statement do to this linked list?
list
"A"
"B"
"C"
1. list = list.next;
list
"A"
"B"
"C"
Fall 2020
15-121 (Reid-Miller)
11
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- 4 3 stacks queues and linked lists university of pennsylvania
- singly linked lists cornell university
- linked list basics stanford university
- linked data structures i singly linked lists
- singly linked list class carnegie mellon university
- doubly linked lists
- lecture 09 structs and linked lists carnegie mellon university
- an introduction to linear linked list knight foundation school of
- linked lists and iterators university of bridgeport
- lecture 11 array of linked lists carnegie mellon university
Related searches
- add method linked list java
- java linked list insert in order
- create linked list in java
- for each in a linked list java
- linked list method java
- linked list java tutorial
- linked list java code
- java linked list methods
- linked list in java
- doubly linked list in java
- singly linked list in java
- singly linked list implementation java