Singly Linked Lists - Lehman
[Pages:5]Singly Linked Lists
Presentation for use with the textbook Data Structures and Algorithms in Java, 6th edition, by M. T. Goodrich, R. Tamassia, and M. H. Goldwasser, Wiley, 2014
Singly Linked Lists
3/18/14
? 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists
1
Singly Linked List
!
!
head
A singly linked list is a concrete data structure consisting of a sequence of nodes, starting from a head pointer
Each node stores
n element
n link to the next node
next
element
node
A
B
? 2014 Goodrich, Tamassia, Goldwasser
C
Singly Linked Lists
D
2
1
Singly Linked Lists
A Nested Node Class
3/18/14
? 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists
3
Accessor Methods
? 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists
4
2
Singly Linked Lists
3/18/14
Inserting at the Head
? Allocate new
node
? Insert new
element
? Have new
node point to old head
? Update head
to point to new node
? 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists
5
Inserting at the Tail
?Allocate a new
node
?Insert new
element
?Have new node
point to null
?Have old last node
point to new node
?Update tail to
point to new node
? 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists
6
3
Singly Linked Lists
Java Methods
3/18/14
? 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists
7
Removing at the Head
? Update head
to point to next node in the list
? Allow
garbage collector to reclaim the former first node
? 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists
8
4
Singly Linked Lists
Java Method
3/18/14
? 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists
9
Removing at the Tail
? Removing at the tail of a singly linked list is
not efficient!
? There is no constant-time way to update the
tail to point to the previous node
? 2014 Goodrich, Tamassia, Goldwasser Singly Linked Lists
10
5
................
................
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
- dog food brands linked to heart disease
- grain free dog food linked to cardiomyopathy
- dog foods linked to heart disease
- singly linked list in java
- singly linked list implementation java
- singly linked list c code
- singly linked list structures
- singly linked list example
- singly linked list python
- linked lists in java
- lists of lists epa
- epa lists of lists excel