java chapter3.ppt

Data Structure
Software College Northeastern University
Chapter 3
Linked Lists
Data Structure
Software College Northeastern University
Overview
Linked Lists
Programming mon Error
Doubly Linked Lists
Circularly Linked Lists
examples
Cursors Implementation of Linked Lists
Data Structure
Software College Northeastern University
Variable-length arrays?
Direct access to element (By indexing)
Array size is fixed-length
-To expand them, you create a new, longer array, and copy the contents of the old array into the new array
This is used by function realloc() in C
This is slow!
Linear time Insertion/Removal due to shift elements
due to contiguous storage in memory
Half of the list needs to be moved for either operations
Data Structure
Software College Northeastern University
Variable-length arrays?
Solution:
-The list is not need to store contiguously.
-Attach a pointer to each item in the array, which points to the next item.
-provides the ability to add or remove the items anywhere in the list in constant time
This is a linked list
Linked lists are unbounded
(maximum number of items limited only by memory)
Data Structure
Software College Northeastern University
The Linked List data structure
[0]
[1]
[2]
array
A
B
C
Array
Head
A
B
C
Linked list
An data item plus its pointer is called a node
A node contains data item and one or more links.
- The link is a reference to a node.
- The link of last node is set to NULL
a “head” which is a pointer to the first node in the
linked list
node
Data Structure
Software College Northeastern University
以线性表中第一个数据元素的存储地址作为线性表的地址,称作线性表的头指针。
头结点
a1 a2 …... an ^
头指针
头指针
有时为了操作方便,在第一个结点之前虚加一个“头结点”,以指向头结点的指针为链表的头指针。
空指针
线性表为空表时,
头结点的指针域为空

Data Structure
Software College Northeastern University
ZHAO
QIAN
SUN
LI
ZHOU
WU
ZHENG
WANG
^
H
43
13
1
NULL
37
7
19
25
Data Item
Links
LI
QIAN
SUN
WANG
WU
ZHAO
ZHENG
ZHOU
Address
1
7
13
19
25
31
37
43