实现LinkedList类
1.链表类LinkedList类中含有以下元素
- 一个内部类，含有它自己的构造器
- 一个构造器，用于初始化空链表
- 方法toString，reset，locate，insert，delete
1.内部类
class Node {
int data;
Node next;
public Node( int paraValue ) {
data = paraValue;
next = null;
} // Of the constructor
} // Of class Node
2.构造器
public LinkedList( ) {
header = new Node( 0 );
// header.next = null; // Redundant
} // Of the first constructor
3.toString方法
空链表则返回“empty”，否则遍历链表，将其所有元素和“，”拼接成字符串后返回
public String toString( ) {
String resultString = "";
if( header.next == null ) {
return "empty";
} // Of if
Node tempNode = header.next;
while( tempNode != null ) {
resultString += tempNode.data + ", ";
tempNode = tempNode.next;
} // Of while
return resultString;
} // Of toString
时间复杂度：
O
(
n
)
O(n)
O(n)，需遍历链表
空间复杂度：
O
(
1
)
O(1)
O(1)
4.reset方法
将头结点的指针置空即可
public void reset( ) {
header.next = null;
} // Of reset
时间复杂度：
O
(
1
)
O(1)
O(1)
空间复杂度：
O
(
1
)
O(1)
O(1)
5.locate方法：按值返回其位置
遍历链表以查找值，若找到，则返回位置（即它是链表中的第几号元素），否则返回-1表示该值不在链表中。
public int locate( int paraValue ) {
int tempPosition = -1;
Node tempNode = header.next;
int tempCurrentPosition = 0;
while( tempNode != null ) {
if( tempNode.data == paraValue ) {
tempPosition = tempCurrentPosition;
break;
} // Of if
tempNode = tempNode.next;
tempCurrentPosition++;
} // Of while
return tempPosition;
} // Of locate
时间复杂度：
O
(
n
)
O(n)
O(n)，需遍历链表
空间复杂度：
O
(
1
)
O(1)
O(1)
6.insert方法：插入一个值到指定位置
遍历链表，若链表遍历结束还未找到第paraPosition - 1个位置，则位置非法，显示对应信息并返回false表示插入失败。否则找到第paraPosition - 1个位置，构造一个新节点并在之后插入即可。
插入步骤如下：
tempNewNode.next = tempNode.next; tempNode.next = tempNewNode;
代码如下：
public boolean insert( int paraPosition, int paraValue ) {
Node tempNode = header;
Node tempNewNode;
for( int i = 0; i < paraPosition; i++ ) {
if( tempNode.next == null ) {
System.out.println("The position " + paraPosition + " is illegal.");
return false;
} // Of if
tempNode = tempNode.next;
} // Of for i
// Construct a new node.
tempNewNode = new Node( paraValue );
// Now link them.
tempNewNode.next = tempNode.next;
tempNode.next = tempNewNode;
return true;
} // Of insert
时间复杂度：
O
(
n
)
O(n)
O(n)，需遍历链表
空间复杂度：
O
(
1
)
O(1)
O(1)
注意：这里的insert方法是将值插入到给定的位置，故需要遍历链表导致
O
(
n
)
O(n)
O(n)的时间复杂度。若是仅将新节点插入到链表中的insert，可以在有头节点引用的链表中进行头部插入，或在有尾节点引用的链表中进行尾部插入，只需要
O
(
1
)
O(1)
O(1)的时间复杂度。因为此时只需要改变几个节点的next指向即可完成插入，和链表中的元素个数
n
n
n无关。
7.delete方法：删除指定位置节点
若是空表，则不能删除，显示对应信息并返回false，否则，遍历链表以查找第paraPosition - 1个位置，若paraPosition - 1个节点不存在或者paraPosition - 1个节点的next为null，则不存在第paraPosition个节点，显示对应信息并返回false。若找到paraPosition - 1个节点且其next不为null，则调整next指向以删除结点，返回true。
代码如下：
public boolean delete( int paraPosition ) {
if( header.next == null ) {
System.out.println("Cannot delete element from an empty list.");
return false;
} // Of if
Node tempNode = header;
for( int i = 0; i < paraPosition; i++ ) {
if( tempNode.next.next == null ) {
System.out.println("The position " + paraPosition + " is illegal.");
return false;
} // Of if
tempNode = tempNode.next;
} // Of for i
tempNode.next = tempNode.next.next;
return true;
} // Of delete
时间复杂度：
O
(
n
)
O(n)
O(n)，需遍历链表
空间复杂度：
O
(
1
)
O(1)
O(1)
java中删除一个节点，不用手动释放该节点占用的空间，因为垃圾收集器将为任何无法访问的对象释放内存。这一点与C语言是不相同的，C语言中必须记得手动释放空间。
测试代码如下：
public static void main( String args[ ] ) {
LinkedList tempFirstList = new LinkedList( );
System.out.println("Initialized, the list is: " + tempFirstList.toString( ) );
for( int i = 0; i < 5; i++ ) {
tempFirstList.insert( 0, i );
} // Of for i
System.out.println("Inserted, the list is: " + tempFirstList.toString( ) );
tempFirstList.insert( 6, 9 );
tempFirstList.delete( 4 );
tempFirstList.delete( 2 );
System.out.println("Deleted, the list is: " + tempFirstList.toString( ) );
for( int i = 0; i < 5; i++ ) {
tempFirstList.delete( 0 );
System.out.println("Looped delete, the list is: " + tempFirstList.toString( ) );
} // Of for i
} // Of main
测试结果如下：
- java的垃圾收集器机制简化了内存管理。
- 在链表中java的引用起到了和C中的指针相同的作用。
