1.实现思路：通过双链表来实现，并且保留该表两端的引用。
2.实现设计：
a. MyLinkedList类：包含到两端的链，表的大小以及一些方法。
b. Node类：一个节点包含数据以及前一个节点的链和下一个节点的链，以及其构造方法。
c. LinkedListIterator类：实现接口Iterator，提供next，hasNext，remove方法的实现。
3. 具体实现过程---Coding：
a. 实现Node类：
//定义节点，类型为AnyType
private static class Node<AnyType>{
//通过构造函数，创建一个节点
public Node(AnyType d, Node<AnyType> p, Node<AnyType> n){
data = d;
prev = p;
next = n;
}
//当前结点数据
public AnyType data;
//向前驱点
public Node<AnyType> prev;
//向后驱点
public Node<AnyType> next;
}
b. 定义一些常量：
public class MyLinkedList<Object> implements Iterable<Object> {
//定义当前长度
private int theSize;
//定义操作次数，增加，删除等影响结构的操作
private int modCount = 0;
//定义开始标记
private Node<Object> beginMarker;
//定义结束标记
private Node<Object> endMarker;
}
c.构造函数以及初始化操作：
//创建时，清空所有之前的数据
public MyLinkedList(){
doClear();
}
//清空操作
public void clear(){
doClear();
}
//实现具体的清空操作
public void doClear() {
//定义开始节点
beginMarker = new Node<Object>(null,null,null);
//定义结束节点，注意这里将开始节点作为结束节点的向前节点
endMarker = new Node<Object>(null, beginMarker, null);
//将结束节点作为开始节点的向后节点
beginMarker.next = endMarker;
//初始化大小为0
theSize = 0;
//操作加1
modCount ++;
}
//返回当前长度
public int size(){
return theSize;
}
//判断当前链表是否为空
public boolean isEmpty(){
return theSize == 0;
}
d. get操作，获取到节点以及节点数据等
/**
* 根据链表位置获取到对应的数据：通过调用getNode方法获取到当前结点，
* 再获取到当前结点的数据
* @param idx 传入的位置
* @return
*/
public Object get(int idx){
return getNode(idx).data;
}
/**
* 获取到对应位置的节点：调用具体的getNode方法去获取
* @param idx
* @return
*/
private Node<Object> getNode(int idx){
return getNode(idx, 0 , size());
}
/**
* 实现根据位置获取到节点
* @param idx 当前位置
* @param lower 开始位置
* @param upper 结束位置
* @return
*/
private Node<Object> getNode(int idx, int lower, int upper){
//定义一个临时节点
Node<Object> p;
//若传入的位置超出范围，则抛出异常
if (idx < lower || idx > upper)
throw new IndexOutOfBoundsException();
//若当前位置在左边，则从开始出进行向后遍历
if (idx < size() / 2){
//移动到开始处
p = beginMarker;
//遍历直到到达所要求的位置
for (int i = 0; i < idx; i ++){
p = p.next;
}
}
//若当前位置在右边，则从尾部开始进行向前遍历
else {
p = endMarker;
for (int i = size(); i > idx; i --){
p = p.prev;
}
}
return p;
}
e. set操作，用于更新节点数据：
/**
* 更新数据操作
* @param idx 传入的链表位置
* @param newVal 更新的数据
* @return
*/
public Object set(int idx, Object newVal){
//获取到对应位置的节点
Node<Object> p = getNode(idx);
//获取到当前数据
Object oldVal = p.data;
p.data = newVal;
//返回原来的数据
return oldVal;
}
f. 添加操作：主要理解addBefore操作
/**
* 实现默认方式添加元素
* @param x
* @return
*/
public boolean add(Object x){
//调用add方法，添加到尾部
add(size(), x);
return true;
}
/**
* 实现添加到具体的某个位置中
* @param idx
* @param x
*/
public void add(int idx, Object x) {
addBefore(getNode(idx), x);
}
/**
* 实现具体的添加操作
* @param p 当前位置的节点
* @param x 节点数据
*/
private void addBefore(Node<Object> p , Object x){
//根据p节点创建一个新的节点
Node<Object> newNode = new Node<Object>(x, p.prev, p);
//连接新节点与前后两个节点
newNode.prev.next = newNode;
p.prev = newNode;
//长度和操作次数++
theSize ++;
modCount ++;
}
添加操作示意图：
add_node
//实际上，通过构造函数，便完成了示意图中的1和2操作
Node<Object> newNode = new Node<Object>(x, p.prev, p);
//实现了操作3
newNode.prev.next = newNode;
//实现了操作4
p.prev = newNode;
g. 实现删除节点操作：
/**
* 实现移除某个位置的节点
* @param idx
* @return
*/
public Object remove(int idx){
return remove(getNode(idx));
}
/**
* 具体移除节点操作
* @param p 传入要移除的节点
* @return
*/
private Object remove(Node<Object> p){
//移除当前节点
p.next.prev = p.prev;
p.prev.next = p.next;
//长度--
theSize --;
//操作次数++
modCount ++;
//返回移除节点的数据
return p.data;
}
删除示意图：
delete_node.png
h. 实现查找元素位置操作：
/**
* 实现查找链表中首先出现的元素位置
* @param x
* @return
*/
public int indexOf(Object x){
int index = 0;
//若传入的数据为空
if (x == null){
//遍历链表，查找是否含有数据为null的节点，找到后立即返回当前位置
for (Node<Object> node = beginMarker.next; node != endMarker; node = node.next){
if (node.data == null){
return index;
}
index ++;
}
}
//数据不为空时，使用equals方法进行比较
else {
for (Node<Object> node = beginMarker.next; node != endMarker; node = node.next){
if (x.equals(node.data)){
return index;
}
index ++;
}
}
return -1;
}
/**
* 实现查找链表中元素最后出现的位置
* 从尾节点开始向前遍历搜查
* @param x
* @return
*/
public int lastIndexOf(Object x){
int index = size() - 1;
if (x == null){
for (Node<Object> node = endMarker.prev; node != beginMarker; node = node.prev){
if (node.data == null){
return index;
}
index --;
}
} else {
for (Node<Object> node = endMarker.prev; node != beginMarker; node = node.prev){
if (x.equals(node.data)){
return index;
}
index --;
}
}
return -1;
}
i. 实现LinkedListIterator类：
private class LinkedListIterator implements Iterator<Object>{
//定义当前结点为始节点的下一个节点
private Node<Object> current = beginMarker.next;
//定义操作次数
private int expectedModCount = modCount;
//判断是否可以进行删除
private boolean okToRemove = false;
//判断是否存在下一个节点
@Override
public boolean hasNext() {
return current != endMarker;
}
//获取到下一个节点数据
@Override
public Object next() {
//操作次数不一致抛出异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//不存在下一个节点，抛出异常
if (!hasNext())
throw new NoSuchElementException();
//获取到下一个节点的数据，并设置okToRemove为true，表示可以进行删除
Object nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
//进行删除操作
public void remove(){
//操作次数不一致，抛出异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//无法进行删除操作，必须先进行next，才可以进行remove操作
if (!okToRemove)
throw new IllegalStateException();
//调用链表中的remove方法进行删除操作，注意传入的是current.pre节点
MyLinkedList.this.remove(current.prev);
//操作次数++
expectedModCount ++;
okToRemove = false;
}
}
完整代码如下：
/**
* Created by Administrator on 2017/3/5/005.
* 实现自定义LinkedList
*/
public class MyLinkedList<Object> implements Iterable<Object> {
//定义当前长度
private int theSize;
//定义操作次数，增加，删除等影响结构的操作
private int modCount = 0;
//定义开始标记
private Node<Object> beginMarker;
//定义结束标记
private Node<Object> endMarker;
//定义节点，类型为AnyType
private static class Node<AnyType>{
//通过构造函数，创建一个节点
public Node(AnyType d, Node<AnyType> p, Node<AnyType> n){
data = d;
prev = p;
next = n;
}
//当前结点数据
public AnyType data;
//向前驱点
public Node<AnyType> prev;
//向后驱点
public Node<AnyType> next;
}
//创建时，清空所有之前的数据
public MyLinkedList(){
doClear();
}
//清空操作
public void clear(){
doClear();
}
//实现具体的清空操作
public void doClear() {
//定义开始节点
beginMarker = new Node<Object>(null,null,null);
//定义结束节点，注意这里将开始节点作为结束节点的向前节点
endMarker = new Node<Object>(null, beginMarker, null);
//将结束节点作为开始节点的向后节点
beginMarker.next = endMarker;
//初始化大小为0
theSize = 0;
//操作加1
modCount ++;
}
//返回当前长度
public int size(){
return theSize;
}
//判断当前链表是否为空
public boolean isEmpty(){
return theSize == 0;
}
/**
* 根据链表位置获取到对应的数据：通过调用getNode方法获取到当前结点，
* 再获取到当前结点的数据
* @param idx 传入的位置
* @return
*/
public Object get(int idx){
return getNode(idx).data;
}
/**
* 更新数据操作
* @param idx 传入的链表位置
* @param newVal 更新的数据
* @return
*/
public Object set(int idx, Object newVal){
//获取到对应位置的节点
Node<Object> p = getNode(idx);
//获取到当前数据
Object oldVal = p.data;
p.data = newVal;
//返回原来的数据
return oldVal;
}
/**
* 获取到对应位置的节点：调用具体的getNode方法去获取
* @param idx
* @return
*/
private Node<Object> getNode(int idx){
return getNode(idx, 0 , size());
}
/**
* 实现根据位置获取到节点
* @param idx 当前位置
* @param lower 开始位置
* @param upper 结束位置
* @return
*/
private Node<Object> getNode(int idx, int lower, int upper){
//定义一个临时节点
Node<Object> p;
//若传入的位置超出范围，则抛出异常
if (idx < lower || idx > upper)
throw new IndexOutOfBoundsException();
//若当前位置在左边，则从开始出进行向后遍历
if (idx < size() / 2){
//移动到开始处
p = beginMarker;
//遍历直到到达所要求的位置
for (int i = 0; i < idx; i ++){
p = p.next;
}
}
//若当前位置在右边，则从尾部开始进行向前遍历
else {
p = endMarker;
for (int i = size(); i > idx; i --){
p = p.prev;
}
}
return p;
}
/**
* 实现默认方式添加元素
* @param x
* @return
*/
public boolean add(Object x){
//调用add方法，添加到尾部
add(size(), x);
return true;
}
/**
* 实现添加到具体的某个位置中
* @param idx
* @param x
*/
public void add(int idx, Object x) {
addBefore(getNode(idx), x);
}
/**
* 实现具体的添加操作
* @param p 当前位置的节点
* @param x 节点数据
*/
private void addBefore(Node<Object> p , Object x){
//实际上，通过构造函数，便完成了示意图中的1和2操作
Node<Object> newNode = new Node<Object>(x, p.prev, p);
//实现了操作3
newNode.prev.next = newNode;
//实现了操作4
p.prev = newNode;
//长度和操作次数++
theSize ++;
modCount ++;
}
/**
* 实现移除某个位置的节点
* @param idx
* @return
*/
public Object remove(int idx){
return remove(getNode(idx));
}
/**
* 具体移除节点操作
* @param p 传入要移除的节点
* @return
*/
private Object remove(Node<Object> p){
//移除当前节点
p.next.prev = p.prev;
p.prev.next = p.next;
//长度--
theSize --;
//操作次数++
modCount ++;
//返回移除节点的数据
return p.data;
}
/**
* 获取到第一个节点数据
* @return
*/
public Object getFirst(){
//先判断链表是否为空，为空则抛出异常
if (isEmpty()){
throw new NoSuchElementException();
}
return beginMarker.next.data;
}
//获取到链表中的最后一个节点数据
public Object getLast(){
if (isEmpty()){
throw new NoSuchElementException();
}
return endMarker.prev.data;
}
//移除链表中第一个节点
public Object removeFirst(){
if (isEmpty()){
throw new NoSuchElementException();
}
//调用remove方法，移除开始节点的下一个节点即可
return remove(beginMarker.next);
}
//移除链表中的最后一个节点
public Object removeLast(){
if (isEmpty()){
throw new NoSuchElementException();
}
//调用remove方法，移除结束节点的上一个节点即可
return remove(endMarker.prev);
}
//从头部开始添加节点
public void addFirst(Object x){
//将添加节点设置为头节点即可
addBefore(beginMarker.next, x);
}
//从尾部添加节点
public void addLast(Object x){
add(x);
}
//添加一个Collection集合
public void addAll(Collection<Object> collection){
//添加集合为空，则抛出异常
if (collection == null){
throw new NullPointerException();
}
//遍历集合，并逐个添加到链表中
for (Object aCollection : collection) {
add(aCollection);
}
}
//判断链表中是否含有某个元素，调用indexOf方法即可
public boolean contains(Object x){
return indexOf(x) != -1;
}
/**
* 实现查找链表中首先出现的元素位置
* @param x
* @return
*/
public int indexOf(Object x){
int index = 0;
//若传入的数据为空
if (x == null){
//遍历链表，查找是否含有数据为null的节点，找到后立即返回当前位置
for (Node<Object> node = beginMarker.next; node != endMarker; node = node.next){
if (node.data == null){
return index;
}
index ++;
}
}
//数据不为空时，使用equals方法进行比较
else {
for (Node<Object> node = beginMarker.next; node != endMarker; node = node.next){
if (x.equals(node.data)){
return index;
}
index ++;
}
}
return -1;
}
/**
* 实现查找链表中元素最后出现的位置
* 从尾节点开始向前遍历搜查
* @param x
* @return
*/
public int lastIndexOf(Object x){
int index = size() - 1;
if (x == null){
for (Node<Object> node = endMarker.prev; node != beginMarker; node = node.prev){
if (node.data == null){
return index;
}
index --;
}
} else {
for (Node<Object> node = endMarker.prev; node != beginMarker; node = node.prev){
if (x.equals(node.data)){
return index;
}
index --;
}
}
return -1;
}
/**
* 实现链表的遍历
* @return
*/
public Iterator<Object> iterator(){
return new LinkedListIterator();
}
private class LinkedListIterator implements Iterator<Object>{
//定义当前结点为始节点的下一个节点
private Node<Object> current = beginMarker.next;
//定义操作次数
private int expectedModCount = modCount;
//判断是否可以进行删除
private boolean okToRemove = false;
//判断是否存在下一个节点
@Override
public boolean hasNext() {
return current != endMarker;
}
//获取到下一个节点数据
@Override
public Object next() {
//操作次数不一致抛出异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//不存在下一个节点，抛出异常
if (!hasNext())
throw new NoSuchElementException();
//获取到下一个节点的数据，并设置okToRemove为true，表示可以进行删除
Object nextItem = current.data;
current = current.next;
okToRemove = true;
return nextItem;
}
//进行删除操作
public void remove(){
//操作次数不一致，抛出异常
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
//无法进行删除操作，必须先进行next，才可以进行remove操作
if (!okToRemove)
throw new IllegalStateException();
//调用链表中的remove方法进行删除操作，注意传入的是current.pre节点
MyLinkedList.this.remove(current.prev);
//操作次数++
expectedModCount ++;
okToRemove = false;
}
}
}
测试代码：
public class LinkedListTest {
public static void main(String[] args){
//进行添加操作
MyLinkedList<String> myLinkedList = new MyLinkedList<>();
myLinkedList.add("Java");
myLinkedList.add("C++");
myLinkedList.add("Python");
myLinkedList.add(2, "PHP");
//遍历结果
printLinkedList(myLinkedList.iterator());
//进行删除和更新操作
myLinkedList.remove(2);
myLinkedList.set(1,"JavaScript");
printLinkedList(myLinkedList.iterator());
//获取到首尾元素
System.out.println("first data : " + myLinkedList.getFirst());
System.out.println("last data : " + myLinkedList.getLast());
//移除首尾节点
myLinkedList.removeFirst();
myLinkedList.removeLast();
printLinkedList(myLinkedList.iterator());
//分别从首尾部添加
myLinkedList.addFirst("C#");
myLinkedList.addLast("CSS");
printLinkedList(myLinkedList.iterator());
//清空操作
myLinkedList.clear();
printLinkedList(myLinkedList.iterator());
//addAll方法
List<String> list = new ArrayList<>();
list.add("JAVA");
list.add("C++");
list.add("C");
list.add("JavaScript");
list.add("C");
list.add("HTML");
myLinkedList.addAll(list);
printLinkedList(myLinkedList.iterator());
//查找元素
System.out.println("是否存在CSS教程: " + myLinkedList.contains("CSS"));
System.out.println("是否存在HTML教程: " + myLinkedList.contains("HTML"));
System.out.println("C教程开始的位置为: " + myLinkedList.indexOf("C"));
System.out.println("C教程最后的位置为: " + myLinkedList.lastIndexOf("C"));
}
private static void printLinkedList(Iterator<String> iterator){
System.out.print("当前链表为: ");
while (iterator.hasNext()){
System.out.print(iterator.next() + " ");
}
System.out.println();
}
}
输出结果：
当前链表为: Java C++ PHP Python
当前链表为: Java JavaScript Python
first data : Java
last data : Python
当前链表为: JavaScript
当前链表为: C# JavaScript CSS
当前链表为:
当前链表为: JAVA C++ C JavaScript C HTML
是否存在CSS教程: false
是否存在HTML教程: true
C教程开始的位置为: 2
C教程最后的位置为: 4
