废话不多说切入到正文，众所周知LinkedList是用链表算法实现，其优点是：
1、插入速度快
2、删除速度快
缺点:
1、检索速度慢
熟悉链表算法就知道是什么原因，接下来详细讲解一下链表算法，首先给大家看一下我简单实现的链表node：
/**
*
* @author sheyong
*
* @param <T>
*/
class LinkNode<T> {
public LinkNode(LinkNode<T> next, LinkNode<T> previous, T obj) {
this.next = next;
this.previous = previous;
this.obj = obj;
}
private LinkNode<T> next;//下一个节点
private LinkNode<T> previous;//上一个节点
private T obj;
/**
* 删除节点
*/
public void remove() {
next.previous = previous;
previous.next = next;
}
/**
* 修改节点
*/
public void set(T t) {
LinkNode<T> link = new LinkNode<T>(next, previous, t);
next.previous = link;
previous.next = link;
}
public String toString() {
return obj.toString();
}
}
从这段代码可以看出：
1、当前对象保存着上一个和下一个对象的引用
private LinkNode<T> next;//下一个节点
private LinkNode<T> previous;//上一个节点
2、remove一个对象（这里有点不好理解，你可以把链表想成一个锁链，形象思维。）：
2.1、当前对象的previous对象的next对先指向的当前对象next。
2.2、当前对象的next对象previous指向当前对先previous。
next.previous = previous;//前与后相连
previous.next = next;//后与前相连
这样就实际上把要删除的对象挤出链接里了。
3、set一个对象(理解删除这里就比较好理解)：
1、创建一个新对象，这个对象的next和previous与当前对象相同。
2、把this.next.previous指向新创建的对象。
3、把this.previous.next指向新创建的对象。
public void set(T t) {
LinkNode<T> link = new LinkNode<T>(next, previous, t);//新对象
next.previous = link;//改变next
previous.next = link;//改变previous
}
这样这个对象就被替换掉了。
接下来给大家介绍一下整个链(LinkList):
/**
*
* @author sheyong
*
*/
class LinkList {
LinkNode<T> head = new LinkNode<T>(null, null, null);// 头节点
public LinkList() {
head.next = head;
head.previous = head;
// 首尾相连
}
/**
* 返回头节点
* @Author : sheyong
*/
public LinkNode<T> getFirst() {
return head;
}
/**
* 返回最后一个节点
* @Author : sheyong
*/
public LinkNode<T> getLast() {
LinkNode<T> node = head.previous;// 返回最后一个节点
if (node == head) {
return null;
}
return node;
}
/**
* 将节点添加到头节点后
* @Author : sheyong
*/
public LinkNode<T> addFirst(T element) {
return addAfter(element, head);
}
public LinkNode<T> addAfter(T e, LinkNode<T> node) {
LinkNode<T> newNode = new LinkNode<T>(node.next, node, e);
newNode.previous.next = newNode;
newNode.next.previous = newNode;
size++;
return newNode;
}
/**
* 将节点添加到头节点后
* @Author : sheyong
*/
public LinkNode<T> addLast(T e) {
return addAfter(e, head.previous);
}
/*
* @see java.lang.Object#toString()
*/
public String toString() {
String tempStr = "[" + head.next;
LinkNode<T> temp = head.next;
while ((temp = temp.next) != head) {
tempStr += " " + temp;
}
return tempStr + "]";
}
}
大家仔细看看toString方法运行过程，你就能体会到链表的妙笔之处:
1、链表的一个标志是head也就是他的头节点。
2、此链表是一个链环，尾部的next指向头部（也就是当this.next==head的时候此node就是尾部）
3、通过n次temp = temp.next可以找到链表的尾部。
介绍到这里，大家可以把链表联想到集合中来(java中LinkedList就是通过此算法实现)：
大家可以把add操作想成往链表插入元素，把set操作想成修改元素，把index操作想成取到元素......现在的问题就是控制index(在这里给出本人实现的MyLinkedList)：
6 个解决方案
#1
public class MyLinkedList<T> extends AbstractSequentialList<T> implements
Collection<T> {
private LinkList list = new LinkList();
private int size;
public int size() {
return size;
}
public boolean isEmpty() {
return list.head.next == list.head;
}
public boolean add(T e) {
list.addAfter(e, list.getFirst().previous);
return true;
}
public String toString() {
return list.toString();
}
/**
*
* @author sheyong
*
*/
class LinkList {
LinkNode<T> head = new LinkNode<T>(null, null, null);// 头节点
public LinkList() {
head.next = head;
head.previous = head;
// 首尾相连
}
/**
* 返回头节点
* @Author : sheyong
*/
public LinkNode<T> getFirst() {
return head;
}
/**
* 返回最后一个节点
* @Author : sheyong
*/
public LinkNode<T> getLast() {
LinkNode<T> node = head.previous;// 返回最后一个节点
if (node == head) {
return null;
}
return node;
}
/**
* 将节点添加到头节点后
* @Author : sheyong
*/
public LinkNode<T> addFirst(T element) {
return addAfter(element, head);
}
public LinkNode<T> addAfter(T e, LinkNode<T> node) {
LinkNode<T> newNode = new LinkNode<T>(node.next, node, e);
newNode.previous.next = newNode;
newNode.next.previous = newNode;
size++;
return newNode;
}
/**
* 将节点添加到头节点后
* @Author : sheyong
*/
public LinkNode<T> addLast(T e) {
return addAfter(e, head.previous);
}
/*
* @see java.lang.Object#toString()
*/
public String toString() {
String tempStr = "[" + head.next;
LinkNode<T> temp = head.next;
while ((temp = temp.next) != head) {
tempStr += " " + temp;
}
return tempStr + "]";
}
}
/**
*
* @author sheyong
*
* @param <T>
*/
class LinkNode<T> {
public LinkNode(LinkNode<T> next, LinkNode<T> previous, T obj) {
this.next = next;
this.previous = previous;
this.obj = obj;
}
private LinkNode<T> next;//下一个节点
private LinkNode<T> previous;//上一个节点
private T obj;
/**
* 删除节点
*/
public void remove() {
next.previous = previous;//前与后相连
previous.next = next;//后与前相连
}
/**
* 修改节点
*/
public void set(T t) {
LinkNode<T> link = new LinkNode<T>(next, previous, t);//新对象
next.previous = link;//改变next
previous.next = link;//改变previous
}
public String toString() {
return obj.toString();
}
}
/**
*
* @author sheyong
*
* @param <T>
*/
public ListIterator<T> listIterator(int index) {
return this.new MyLinkedListIterator(index);
}
private class MyLinkedListIterator implements ListIterator<T> {
private LinkNode<T> current = (LinkNode<T>) list.getFirst();// 当前对象
private int nextIndex;// 下一个索引
public MyLinkedListIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("index:" + index + " ?");
if (index > size >> 1) {
for (nextIndex = size; nextIndex > index; nextIndex--) {
current = current.previous;
}
} else {
for (nextIndex = 0; nextIndex < index; nextIndex++) {
current = current.next;
}
}
}
public boolean hasNext() {
return nextIndex != size;
}
public T next() {
if (nextIndex == size)
throw new IndexOutOfBoundsException("越界");
current = current.next;
nextIndex++;
return current.obj;
}
public boolean hasPrevious() {
return nextIndex != 0;
}
public T previous() {
if (nextIndex == 0)
throw new IndexOutOfBoundsException("越界");
current = current.next;
nextIndex--;
return current.obj;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
current.remove();
size--;
nextIndex--;
}
public void set(T e) {
current.set(e);
}
public void add(T e) {
MyLinkedList.this.list.addLast(e);
size++;
}
}
}
#2
没人支持。。。。。。
#3
该回复于2013-01-26 09:35:02被管理员删除
#4
写的很好。谢谢。
#5
谢谢。
#6
写的很好，给你个赞哦
#1
public class MyLinkedList<T> extends AbstractSequentialList<T> implements
Collection<T> {
private LinkList list = new LinkList();
private int size;
public int size() {
return size;
}
public boolean isEmpty() {
return list.head.next == list.head;
}
public boolean add(T e) {
list.addAfter(e, list.getFirst().previous);
return true;
}
public String toString() {
return list.toString();
}
/**
*
* @author sheyong
*
*/
class LinkList {
LinkNode<T> head = new LinkNode<T>(null, null, null);// 头节点
public LinkList() {
head.next = head;
head.previous = head;
// 首尾相连
}
/**
* 返回头节点
* @Author : sheyong
*/
public LinkNode<T> getFirst() {
return head;
}
/**
* 返回最后一个节点
* @Author : sheyong
*/
public LinkNode<T> getLast() {
LinkNode<T> node = head.previous;// 返回最后一个节点
if (node == head) {
return null;
}
return node;
}
/**
* 将节点添加到头节点后
* @Author : sheyong
*/
public LinkNode<T> addFirst(T element) {
return addAfter(element, head);
}
public LinkNode<T> addAfter(T e, LinkNode<T> node) {
LinkNode<T> newNode = new LinkNode<T>(node.next, node, e);
newNode.previous.next = newNode;
newNode.next.previous = newNode;
size++;
return newNode;
}
/**
* 将节点添加到头节点后
* @Author : sheyong
*/
public LinkNode<T> addLast(T e) {
return addAfter(e, head.previous);
}
/*
* @see java.lang.Object#toString()
*/
public String toString() {
String tempStr = "[" + head.next;
LinkNode<T> temp = head.next;
while ((temp = temp.next) != head) {
tempStr += " " + temp;
}
return tempStr + "]";
}
}
/**
*
* @author sheyong
*
* @param <T>
*/
class LinkNode<T> {
public LinkNode(LinkNode<T> next, LinkNode<T> previous, T obj) {
this.next = next;
this.previous = previous;
this.obj = obj;
}
private LinkNode<T> next;//下一个节点
private LinkNode<T> previous;//上一个节点
private T obj;
/**
* 删除节点
*/
public void remove() {
next.previous = previous;//前与后相连
previous.next = next;//后与前相连
}
/**
* 修改节点
*/
public void set(T t) {
LinkNode<T> link = new LinkNode<T>(next, previous, t);//新对象
next.previous = link;//改变next
previous.next = link;//改变previous
}
public String toString() {
return obj.toString();
}
}
/**
*
* @author sheyong
*
* @param <T>
*/
public ListIterator<T> listIterator(int index) {
return this.new MyLinkedListIterator(index);
}
private class MyLinkedListIterator implements ListIterator<T> {
private LinkNode<T> current = (LinkNode<T>) list.getFirst();// 当前对象
private int nextIndex;// 下一个索引
public MyLinkedListIterator(int index) {
if (index < 0 || index > size)
throw new IndexOutOfBoundsException("index:" + index + " ?");
if (index > size >> 1) {
for (nextIndex = size; nextIndex > index; nextIndex--) {
current = current.previous;
}
} else {
for (nextIndex = 0; nextIndex < index; nextIndex++) {
current = current.next;
}
}
}
public boolean hasNext() {
return nextIndex != size;
}
public T next() {
if (nextIndex == size)
throw new IndexOutOfBoundsException("越界");
current = current.next;
nextIndex++;
return current.obj;
}
public boolean hasPrevious() {
return nextIndex != 0;
}
public T previous() {
if (nextIndex == 0)
throw new IndexOutOfBoundsException("越界");
current = current.next;
nextIndex--;
return current.obj;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
current.remove();
size--;
nextIndex--;
}
public void set(T e) {
current.set(e);
}
public void add(T e) {
MyLinkedList.this.list.addLast(e);
size++;
}
}
}
#2
没人支持。。。。。。
#3
该回复于2013-01-26 09:35:02被管理员删除
#4
写的很好。谢谢。
#5
谢谢。
#6
写的很好，给你个赞哦