链表中的每一个元素都包含一个称为节点的结构，每向链表中增加一个元素，就会产生一个与之相关的节点，每个节点与它相邻的节点相连接（这是基础吧，不过在看c的时候没认真看，呼）。
定义节点类如下(使用了泛型，下面有个简单的具体实例)：
class Node<E>{
E element ;
Node<E> next;
public Node(E e){
element = e;
}
}
下面讲解一个储存3个元素的链表的例子，每一个节点储存一个字符串；
1、先声明head(指向第一个节点) 和tai(指向最后一个节点)，刚开始时都是null
Node<E> head = null;
Node<E> tail = null;
//链表为空
2、追加第一个节点
head = new Node<E>("Chicgo")；
last = head;3、追加第二个节点
tail.next = new Node<E>("Denver");
tail = tail.next;3、追加第三个节点
tail.next = new Node<E>("Dallas");
tail = tail.next;每一个节点都包含元素和一个名为next的数据域，next指向下一个元素。如果元素是链表中的最后一个元素。则它的next所包含的为null，用这个特性可以检测某个节点是否为最后一个节点，例如下面的遍历程序：
Node current = head;
while()current !＝null){
System.out.println(current.element);
current = current.next;
}
下面就结合上面的知识给个简单的int类型事例：
//一个节点类，每一个元素都包含了一个称为节点的结构
public class Node{
int element;
Node next ;
public Node(int n){ //元素赋值
element = n;
}
public static void main(String[] args) {
Node head , tail; //申明head和tail
head = new Node(1); //插入第一个元素
tail = head; //head和tail在一起
System.out.println(head.element); //输出第一个元素
tail.next = new Node(2); //插入第二个元素
tail = tail.next;
tail.next =new Node(3);
tail = tail.next;
Node current = head ;
while (current != null){ //遍历寻遍输出
System.out.print(current.element);
current = current.next;
}
}
}
java中有提供LinkedList的类，可以通过导入 java.util.LinkedList来使用，不过书本上有教我们写一个自己的MyLinkedList，便于理解，这对我们掌握链表还是很有必要的。下面我们可以来仔细研究一下MyLinkedList了，有好多方法，不像MyArrayList容易理解，书本上也只是讲了几个方法，剩下的就自己去理解了，也不是很难，这里讲3个吧，就当练习打字。
（补充：head始终指向链表的第一个节点，而tail则始终指向最后一个节点）
1、实现addFirst(e)方法，就是创建第一个节点：
//创建一个包含e元素节点，并放在第一个节点
public void addFirst(E e) {
Node<E> newNode = new Node<E>(e); // 创建一个的节点
newNode.next = head; //新节点的next数据域指向head
head = newNode; // head 指向新的节点
size++; if (tail == null) // 若链表为空，则head和tail都指向新节点
tail = head;
}
（书本上的那个图很好看，但是画不下来==）
2、实现add(index,e)方法，当index为0或则是在最后一个元素时就不说了，直接调用方法addFirst(e)或则addLast(e)就行了，若插入到中间时，假设为current和temp节点之间，则首先从head开始前进找到current的next，并被新节点赋给它，在把新节点的next指向temp，画个图就很容易理解了。
public void add(int index, E e) {
if (index == 0) {
addFirst(e);
}
else if (index >= size) {
addLast(e);
}
else {
Node<E> current = head;
for (int i = 1; i < index; i++) {
current = current.next;
}
Node<E> temp = current.next;
current.next = new Node<E>(e);
(current.next).next = temp;
size++;
}
}3、实现removeLast()方法，如果链表为空就返回null，如果只有一个节点就销毁并且head和tail都变为null,否则最后一个节点销毁，tail指向倒数第二个节点，size减一。
public E removeLast() {
if (size == 0) {
return null;
}
else if (size == 1) {
Node<E> temp = head;
head = tail = null;
size = 0;
return temp.element;
}
else {
Node<E> current = head; //要从head开始遍历，增加了时间
for (int i = 0; i < size - 2; i++) {
current = current.next; //找到倒数第二个节点
}
Node<E> temp = tail; //临时引用temp
tail = current;
tail.next = null;
size--;
return temp.element;
}
}最后在给出MyLinkedList的实现(仅有部分方法实现，还有部分，做作业)：
public class MyLinkedList<E> extends MyAbstractList<E> {
private Node<E> head, tail;
//创建默认链表
public MyLinkedList() {
}
public MyLinkedList(E[] objects) {
super(objects);
}
//获得链表的头
public E getFirst() {
if (size == 0) {
return null;
}
else {
return head.element;
}
}
//获得链表的尾
public E getLast() {
if (size == 0) {
return null;
}
else {
return tail.element;
}
}
//创建一个包含e元素节点，并放在第一个节点
public void addFirst(E e) {
Node<E> newNode = new Node<E>(e); // 创建一个的节点
newNode.next = head; //新节点的next数据域指向head
head = newNode; // head 指向新的节点
size++;
if (tail == null) // 若链表为空，则head和tail都指向新节点
tail = head;
}
//创建一个包含e元素节点，并放在最后一个节点
public void addLast(E e) {
Node<E> newNode = new Node<E>(e);
if (tail == null) {
head = tail = newNode;
}
else {
tail.next = newNode;
tail = tail.next;
}
size++;
}
//将一个元素插入到链表的指定下标处
public void add(int index, E e) {
if (index == 0) {
addFirst(e);
}
else if (index >= size) {
addLast(e);
}
else {
Node<E> current = head;
for (int i = 1; i < index; i++) {
current = current.next;
}
Node<E> temp = current.next;
current.next = new Node<E>(e);
(current.next).next = temp;
size++;
}
}
//删除链表中的的首个元素
public E removeFirst() {
if (size == 0) {
return null;
}
else {
Node<E> temp = head;
head = head.next;
size--;
if (head == null) {
tail = null;
}
return temp.element;
}
}
//删除最后一个元素
public E removeLast() {
if (size == 0) {
return null;
}
else if (size == 1) {
Node<E> temp = head;
head = tail = null;
size = 0;
return temp.element;
}
else {
Node<E> current = head; //要从head开始遍历，增加了时间
for (int i = 0; i < size - 2; i++) {
current = current.next; //找到倒数第二个节点
}
Node<E> temp = tail; //临时引用temp
tail = current;
tail.next = null;
size--;
return temp.element;
}
}
//删除指定下标的元素
public E remove(int index) {
if (index < 0 || index >= size) {
return null;
}
else if (index == 0) {
return removeFirst();
}
else if (index == size - 1) {
return removeLast();
}
else {
Node<E> previous = head;
for (int i = 1; i < index; i++) {
previous = previous.next;
}
Node<E> current = previous.next;
previous.next = current.next;
size--;
return current.element;
}
}
public String toString() {
StringBuilder result = new StringBuilder("[");
Node<E> current = head;
for (int i = 0; i < size; i++) {
result.append(current.element);
current = current.next;
if (current != null) {
result.append(", "); // 插入歌逗号
}
else {
result.append("]"); // 插入]
}
}
return result.toString();
}
//清空
public void clear() {
head = tail = null;
}
/** Return true if this list contains the element o */
public boolean contains(E o) {
System.out.println("Implementation left as an exercise");
return true;
}
/** Return the element from this list at the specified index */
public E get(int index) {
System.out.println("Implementation left as an exercise");
return null;
}
/** Return the index of the head matching element in this list.
* Return -1 if no match. */
public int indexOf(E o) {
System.out.println("Implementation left as an exercise");
return 0;
}
/** Return the index of the last matching element in this list
* Return -1 if no match. */
public int lastIndexOf(E o) {
System.out.println("Implementation left as an exercise");
return 0;
}
/** Replace the element at the specified position in this list
* with the specified element. */
public Object set(int index, E o) {
System.out.println("Implementation left as an exercise");
return null;
}
private static class Node<E> {
E element;
Node<E> next;
public Node(E element) {
this.element = element;
}
}
}
在附上一个测试程序：
public class TestLinkedList {
/** Main method */
public static void main(String[] args) {
// Create a list for strings
MyLinkedList<String> list = new MyLinkedList<String>();
// Add elements to the list
list.add("America"); // Add it to the list
System.out.println("(1) " + list);
list.add(0, "Canada"); // Add it to the beginning of the list
System.out.println("(2) " + list);
list.add("Russia"); // Add it to the end of the list
System.out.println("(3) " + list);
list.addLast("France"); // Add it to the end of the list
System.out.println("(4) " + list);
list.add(2, "Germany"); // Add it to the list at index 2
System.out.println("(5) " + list);
list.add(5, "Norway"); // Add it to the list at index 5
System.out.println("(6) " + list);
list.add(0, "Poland"); // Same as list.addFirst("Poland")
System.out.println("(7) " + list);
// Remove elements from the list
list.remove(0); // Same as list.remove("Australia") in this case
System.out.println("(8) " + list);
list.remove(2); // Remove the element at index 2
System.out.println("(9) " + list);
list.remove(list.size() - 1); // Remove the last element
System.out.println("(10) " + list);
}
}
关于MyArrayList和MyLinkedList的方法的复杂度，看下面的图
