LinkedList简介
LinkedList的基于链表实现的，是一个双端链表，同时也可以用来作为堆栈，队列使用，LinkedList不是线程安全的
MyLinkedList
在实现MyLinkedList前先实现MyList，MyAbstractList，他们的关系如下。
MyLinkedList--->（继承于）MyAbstractList--->（实现）MyList接口--->（实现）java.lang.Iterable接口
通过编写新的LinkedList来实现Java中LinkedList的部分功能
Node节点类
class Node{ E element; Node next; public Node(E e) { element = e; }}
MyList接口定义如下
public interface MyListextends Iterable { public void add(E e); public void add(int index, E e); public void clear(); public boolean contains(E e); public E get(int index); public int indexOf(E e); public boolean isEmpty(); public int lastIndexOf(E e); public boolean remove(E e); public E remove(int index); public E set(int index, E e); public int size();}
MyAbstractList类定义如下
public abstract class MyAbstractListimplements MyList { protected int size = 0; protected MyAbstractList() { } protected MyAbstractList(E[] objects) { for(int i = 0; i < objects.length; i++) { add(objects[i]); } } @Override public void add(E e) { add(size, e); } @Override public boolean isEmpty() { return size == 0; } @Override public int size() { return size; } @Override public boolean remove(E e) { if(indexOf(e) >= 0) { remove(indexOf(e)); return true; }else { return false; } }}
MyLinkedList定义如下
import java.util.Iterator;public class MyLinkedListextends MyAbstractList { private Node head;//头指针 private Node tail;//尾指针 private int size = 0;//链表长度 public MyLinkedList() { } public MyLinkedList(E[] elements) { for(int i = 0; i < elements.length; i++) { addLast(elements[i]); } } public int size() { return size; } protected E getFirst() { // TODO Auto-generated method stub if(size == 0) { return null; }else { return head.element; } } protected E getLast() { // TODO Auto-generated method stub if(size == 0) { return null; }else { return tail.element; } } public void add(E e) { addLast(e); } protected void addFirst(E e) { // TODO Auto-generated method stub Node newNode = new Node<>(e);//创建新的Node newNode.next = head;//将newNode节点的next节点设为head指针指向的节点 head = newNode;//head指针重新指向新加入的节点 size++; if(tail == null) { //如果链表为空，将尾指针也指向newNode tail = newNode; } } protected void addLast(E e) { // TODO Auto-generated method stub Node newNode = new Node<>(e);//创建新的Node if(tail == null) { //如果链表为空，将头指针和尾指针指向newNode head = tail = newNode; }else { tail.next = newNode;//将尾指针指向的Node的next节点设为newNode tail = newNode;//尾指针指向新加入的节点 } size++; } @Override public void add(int index, E e) { // TODO Auto-generated method stub if(index <= 0) { addFirst(e); }else if(index >= size) { addLast(e); }else { Node current = head; for(int i = 1; i < index; i++) { current = current.next; } Node temp = current.next; current.next = new Node (e); (current.next).next = temp; size++; } } //判断下标是否合法 private void checkIndex(int index) { if(index < 0 || index >= size) { throw new IndexOutOfBoundsException("index " + index + " out of bounds"); } } protected E removeFirst() { // TODO Auto-generated method stub if(size == 0) { return null; }else { Node temp = head; head = head.next; size--; if(head == null) { tail = null; } return temp.element; } } protected E removeLast() { // TODO Auto-generated method stub if(size == 0) { return null; }else if(size == 1){ Node temp = head; head = tail = null; size = 0; return temp.element; }else { Node current = head; for(int i = 1; i < size - 1; i++) { current = current.next; } Node temp = tail; tail = current; tail.next = null; size--; return temp.element; } } @Override public E remove(int index) { // TODO Auto-generated method stub if(index < 0 || index >= size) { return null; }else if(index == 0) { return removeFirst(); }else if(index == size - 1) { return removeLast(); }else { Node pervious = head; for(int i = 1; i < index; i++) { pervious = pervious.next; } Node current = pervious.next; pervious.next = current.next; size--; return current.element; } } @Override public String toString() { StringBuilder result = new StringBuilder("["); Node current = head; for(int i = 0; i < size; i++) { result.append(current.element); current = current.next; if(current != null) { result.append("，"); } } return result.toString() + "]"; } @Override public void clear() { // TODO Auto-generated method stub size = 0; head = tail = null; } @Override public boolean contains(E e) { // TODO Auto-generated method stub Node current = head; if(current.element.equals(e)) { return true; } for(int i = 1; i < size; i++) { current = current.next; if(current.element.equals(e)) { return true; } } return false; } @Override public E get(int index) { // TODO Auto-generated method stub checkIndex(index); if(index == 0) { return head.element; }else if(index == size - 1) { return tail.element; }else { Node current = head; for(int i = 1; i < size - 1; i++) { current = current.next; if(i == index) { return current.element; } } } return null; } @Override public int indexOf(E e) { // TODO Auto-generated method stub if(e.equals(head.element)) { return 0; }else { Node current = head; for(int i = 1; i < size; i++) { current = current.next; if(e.equals(current.element)) { return 1; } } } return -1; } @Override public int lastIndexOf(E e) { // TODO Auto-generated method stub if(e.equals(tail.element)) { return size - 1; }else { Node current = head; int result = -1; for(int i = 1; i < size; i++) { current = current.next; if(e.equals(current.element)) { result = i; } } return result; } } @Override public E set(int index, E e) { // TODO Auto-generated method stub checkIndex(index); E result = null; if(index == 0) { result = head.element; head.element = e; return result; }else if(index == size - 1) { result = tail.element; tail.element = e; return result; }else { Node current = head; for(int i = 1; i < size - 1; i++) { current = current.next; if(index == i) { result = current.element; current.element = e; break; } } return result; } } @Override public Iterator iterator() { // TODO Auto-generated method stub return new LinkedListIterator(); } private class LinkedListIterator implements Iterator { private Node current = head; @Override public boolean hasNext() { // TODO Auto-generated method stub return current != null; } @Override public E next() { // TODO Auto-generated method stub E e = current.element; current = current.next; return e; } }}
测试代码如下
public class TestMyLinkedList { public static void main(String[] args) { // TODO Auto-generated method stub// String[] ss = {"China","America","Germany","Canada","France","Germany"}; MyLinkedList list = new MyLinkedList (); System.out.println("测试list的add()方法"); list.add("America"); list.addFirst("China"); list.add("Canada"); list.addLast("France"); list.add(2,"Germany"); list.addLast("Germany"); list.add("Germany"); list.addFirst("Germany"); System.out.println("测试toString()方法：" + list.toString()); System.out.println("测试indexOf()方法：" + list.indexOf("Germany")); System.out.println("测试lastIndexOf()方法：" + list.lastIndexOf("Germany")); System.out.println("测试getFirst()方法：" + list.getFirst()); System.out.println("测试getLast()方法：" + list.getLast()); System.out.println("测试remove()方法"); System.out.println("删除下标为3的元素：" + list.remove(3)); System.out.println("删除第一个元素：" + list.removeFirst()); System.out.println("删除最后的元素：" + list.removeLast()); System.out.println(list.toString()); System.out.println("测试contains()方法：" + list.contains("France")); System.out.println("测试get(int index)方法：" + list.get(3)); System.out.println("测试set()方法：" + list.set(list.size()-1, "Russia")); System.out.println("foreach遍历链表："); for(String s:list) { System.out.print(s.toUpperCase() + " "); } System.out.println(""); list.clear(); System.out.println("测试clear()方法清空链表：" + list); }} 测试结果如下
分析ArrayList和LinkedList的区别
ArrayList是用数组实现的，所以get()和set()方法可以通过下标访问和修改元素，它们是高效的。但是add()和remove()方法的效率很低，因为两个方法需要移动潜在的大量元素
而LinkedList是基于链表实现的，所以插入和删除元素时LinkedList占优势，但是无法直接访问元素，需要在整个链表遍历来访问元素