Core Java (二十二) 列表（List接口）

列表是一个有序的集合（an ordered Collection），可以包含重复的元素，可以包含null，也可以什么都不包含只有null。

List

List接口的所有方法：

boolean
add(E e) Appends the specified element to the end of this list (optional operation).
void
add(int index, E element) Inserts the specified element at the specified position in this list (optional operation).
boolean
addAll(Collection<? extends E> c) Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator (optional operation).
boolean
addAll(int index, Collection<? extends E> c) Inserts all of the elements in the specified collection into this list at the specified position (optional operation).
void
clear() Removes all of the elements from this list (optional operation).
boolean
contains(Object o) Returns  true if this list contains the specified element.
boolean
containsAll(Collection<?> c) Returns  true if this list contains all of the elements of the specified collection.
boolean
equals(Object o) Compares the specified object with this list for equality.
E
get(int index) Returns the element at the specified position in this list.
int
hashCode() Returns the hash code value for this list.
int
indexOf(Object o) Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
boolean
isEmpty() Returns  true if this list contains no elements.
Iterator<E>
iterator() Returns an iterator over the elements in this list in proper sequence.
int
lastIndexOf(Object o) Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
ListIterator<E>
listIterator() Returns a list iterator over the elements in this list (in proper sequence).
ListIterator<E>
listIterator(int index) Returns a list iterator over the elements in this list (in proper sequence), starting at the specified position in the list.
E
remove(int index) Removes the element at the specified position in this list (optional operation).
boolean
remove(Object o) Removes the first occurrence of the specified element from this list, if it is present (optional operation).
boolean
removeAll(Collection<?> c) Removes from this list all of its elements that are contained in the specified collection (optional operation).
boolean
retainAll(Collection<?> c) Retains only the elements in this list that are contained in the specified collection (optional operation).
E
set(int index, E element) Replaces the element at the specified position in this list with the specified element (optional operation).
int
size() Returns the number of elements in this list.
List<E>
subList(int fromIndex, int toIndex) Returns a view of the portion of this list between the specified  fromIndex, inclusive, and  toIndex, exclusive.
Object[]
toArray() Returns an array containing all of the elements in this list in proper sequence (from first to last element).
<T> T[]
toArray(T[] a) Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

实现了List接口的所有类为：

AbstractList, AbstractSequentialList,
ArrayList, AttributeList, CopyOnWriteArrayList,
LinkedList, RoleList, RoleUnresolvedList, Stack, Vector。

其中ArrayList已经由之前的博客写过了，http://www.voidcn.com/article/p-hbjkrbyd-xg.html，这里不再赘述。

重点写一下LinkedList类。

LinkedList

LinkedList是一种链表。在java中，所有链表实际上都是双向链表。

LinkedList实现了Serializable, Cloneable, Iterable<E>, Collection<E>, Deque<E>, List<E>, Queue<E>接口。

LinkedList的构造函数：

LinkedList()

Constructs an empty list. LinkedList(Collection<? extends E> c)

Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

LinkedList的全部方法：

boolean
add(E e) Appends the specified element to the end of this list.
void
add(int index, E element) Inserts the specified element at the specified position in this list.
boolean
addAll(Collection<? extends E> c) Appends all of the elements in the specified collection to the end of this list, in the order that they are returned by the specified collection's iterator.
boolean
addAll(int index, Collection<? extends E> c) Inserts all of the elements in the specified collection into this list, starting at the specified position.
void
addFirst(E e) Inserts the specified element at the beginning of this list.
void
addLast(E e) Appends the specified element to the end of this list.
void
clear() Removes all of the elements from this list.
Object
clone() Returns a shallow copy of this  LinkedList.
boolean
contains(Object o) Returns  true if this list contains the specified element.
Iterator<E>
descendingIterator() Returns an iterator over the elements in this deque in reverse sequential order.
E
element() Retrieves, but does not remove, the head (first element) of this list.
E
get(int index) Returns the element at the specified position in this list.
E
getFirst() Returns the first element in this list.
E
getLast() Returns the last element in this list.
int
indexOf(Object o) Returns the index of the first occurrence of the specified element in this list, or -1 if this list does not contain the element.
int
lastIndexOf(Object o) Returns the index of the last occurrence of the specified element in this list, or -1 if this list does not contain the element.
ListIterator<E>
listIterator(int index) Returns a list-iterator of the elements in this list (in proper sequence), starting at the specified position in the list.
boolean
offer(E e) Adds the specified element as the tail (last element) of this list.
boolean
offerFirst(E e) Inserts the specified element at the front of this list.
boolean
offerLast(E e) Inserts the specified element at the end of this list.
E
peek() Retrieves, but does not remove, the head (first element) of this list.
E
peekFirst() Retrieves, but does not remove, the first element of this list, or returns  null if this list is empty.
E
peekLast() Retrieves, but does not remove, the last element of this list, or returns  null if this list is empty.
E
poll() Retrieves and removes the head (first element) of this list.
E
pollFirst() Retrieves and removes the first element of this list, or returns  null if this list is empty.
E
pollLast() Retrieves and removes the last element of this list, or returns  null if this list is empty.
E
pop() Pops an element from the stack represented by this list.
void
push(E e) Pushes an element onto the stack represented by this list.
E
remove() Retrieves and removes the head (first element) of this list.
E
remove(int index) Removes the element at the specified position in this list.
boolean
remove(Object o) Removes the first occurrence of the specified element from this list, if it is present.
E
removeFirst() Removes and returns the first element from this list.
boolean
removeFirstOccurrence(Object o) Removes the first occurrence of the specified element in this list (when traversing the list from head to tail).
E
removeLast() Removes and returns the last element from this list.
boolean
removeLastOccurrence(Object o) Removes the last occurrence of the specified element in this list (when traversing the list from head to tail).
E
set(int index, E element) Replaces the element at the specified position in this list with the specified element.
int
size() Returns the number of elements in this list.
Object[]
toArray() Returns an array containing all of the elements in this list in proper sequence (from first to last element).
<T> T[]
toArray(T[] a) Returns an array containing all of the elements in this list in proper sequence (from first to last element); the runtime type of the returned array is that of the specified array.

ListIterator接口

但是LinkedList类不能实现将元素插入到链表的中间。而迭代器接口Iterator仅仅有三个方法，也不能满足要求，所以就出现了列表迭代器接口ListIterator<E>可以实现。

下面是ListIterator接口的构造函数

LinkedList
(
)

Constructs an empty list. LinkedList(Collection<? extends E> c)

Constructs a list containing the elements of the specified collection, in the order they are returned by the collection's iterator.

ListIterator接口的全部方法

• add

(E
 e)

• Inserts the specified element into the list (optional operation).
• booleanhasNext()
• Returns true if this list iterator has more elements when traversing the list in the forward direction.
• booleanhasPrevious()
• Returns true if this list iterator has more elements when traversing the list in the reverse direction.
• Enext()
• Returns the next element in the list and advances the cursor position.
• intnextIndex()
• Returns the index of the element that would be returned by a subsequent call to next().
• Eprevious()
• Returns the previous element in the list and moves the cursor position backwards.
• intpreviousIndex()
• Returns the index of the element that would be returned by a subsequent call to previous().
• voidremove()
• Removes from the list the last element that was returned by next() or previous() (optional operation).
• voidset(E e)
• Replaces the last element returned by next() or previous() with the specified element (optional operation).

测试例子：

下面这个测试分别测试了List接口，ListIterator接口以及LinkedList类中的一些重要方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
1package com.xujin;

2

3import java.util.LinkedList;

4import java.util.List;

5import java.util.ListIterator;

6

7public class LinkedListTest{

8   public static void main(String...arg){      

9       Employee jim = new Employee("Jim", 8000);

10      Employee bob = new Employee("Bob", 9000);

11      Manager jin = new Manager("Gin", 10000, 4000);

12      

13      /********List接口中的方法测试************************************************/      

14      List<Employee> staffA = new LinkedList<Employee>();

15      staffA.add(jim);

16      staffA.add(bob);        

17      staffA.add(1,jin);

18      System.out.println(staffA);//[id:1 name:Jim salary:8000.0, id:3 name:Gin salary:10000.0,bonus:4000.0, id:2 name:Bob salary:9000.0]

19      

20      List<Employee> staffB = new LinkedList<Employee>();

21      staffB.add(jim);

22      staffB.add(bob);

23      System.out.println(staffB);//[id:1 name:Jim salary:8000.0, id:2 name:Bob salary:9000.0]

24      

25      System.out.println(staffB.remove(0));//删除index为0的元素并返回这个元素，id:1 name:Jim salary:8000.0

26      staffA.addAll(0, staffB);

27      System.out.println(staffA);//[id:2 name:Bob salary:9000.0, id:1 name:Jim salary:8000.0, id:3 name:Gin salary:10000.0,bonus:4000.0, id:2 name:Bob salary:9000.0]

28

29      staffA.set(0, null);

30      System.out.println(staffA);//[null, id:1 name:Jim salary:8000.0, id:3 name:Gin salary:10000.0,bonus:4000.0, id:2 name:Bob salary:9000.0]

31      

32      /********ListIterator接口中的方法测试************************************************/

33      ListIterator<Employee> aIter = staffA.listIterator();

34      aIter.next();

35      aIter.add(bob);

36      System.out.println(staffA);//[null, id:2 name:Bob salary:9000.0, id:1 name:Jim salary:8000.0, id:3 name:Gin salary:10000.0,bonus:4000.0, id:2 name:Bob salary:9000.0]

37      aIter.previous();

38      aIter.previous();//现在返回的是第一个元素null

39      aIter.set(bob);

40      System.out.println(staffA);//[id:2 name:Bob salary:9000.0, id:2 name:Bob salary:9000.0, id:1 name:Jim salary:8000.0, id:3 name:Gin salary:10000.0,bonus:4000.0, id:2 name:Bob salary:9000.0]

41      

42      

43      while(aIter.hasNext()){

44          aIter.next();

45      }

46      System.out.println(aIter.nextIndex());//5，表明iter已经在链表尾部

47      

48      while(aIter.hasPrevious()){

49          aIter.previous();

50      }

51      System.out.println(aIter.previousIndex());//-1，表明iter已经在链表头部    

52      

53      /********LinkedList类中的方法测试************************************************/

54      staffA.clear();

55      LinkedList<Employee> ll = (LinkedList<Employee>)staffA;

56      ll.addFirst(jin);

57      ll.addLast(jim);

58      System.out.println(ll);//[id:3 name:Gin salary:10000.0,bonus:4000.0, id:1 name:Jim salary:8000.0]

59      

60      ll.removeLast();

61      ll.removeLast();

62      System.out.println(ll);//[]

63  }

64}

65

66class Employee{       

67  public Employee(String name){

68      this.name = name;

69      id = nextId;

70      nextId++;

71  }

72

73  public String toString(){

74      return "id:" + id + " name:" + name +" salary:" + salary;

75  }

76  

77  public Employee(String name, double salary){

78      this(name);//调用另一构造器      

79      this.salary = salary;       

80  }

81  

82  //定义访问器方法

83  public final String getName(){

84      return name;

85  }

86  

87  public double getSalary(){

88      return salary;

89  }

90  

91  public final int getId(){

92      return id;

93  }

94

95  

96  //定义更改器方法

97  public final void setName(String name){

98      this.name = name;

99  }

100 

101 public final void setSalary(double salary){

102     this.salary = salary;

103 }   

104 

105 public final void raiseSalary(double percent){

106     this.salary *= (1 + percent);

107 }

108 

109 //定义变量

110 private String name = "";//实例域初始化

111 private double salary;

112 private int id;

113 private static int nextId = 1;      

114 

115}

116

117class Manager extends Employee{

118 public Manager(String name, double salary, double bonus){

119     super(name, salary);//super在构造器中的使用，可以调用超类的构造器

120     setBonus(bonus);

121 }   

122 

123 public String toString(){

124     return super.toString() + ",bonus:" + bonus;

125 }

126 

127 public double getBonus(){

128     return bonus;

129 }

130 

131 //重写getSalary方法

132 public double getSalary(){

133     double baseSalary = super.getSalary();//调用了超类的getSalary方法

134     return baseSalary + bonus;

135 }

136 

137 public void setBonus(double bonus){

138     this.bonus = bonus;

139 }

140 

141 private double bonus;

142}

143