java模拟单向链表
/**
* 自定义链表
*/
public interface CustomizeList<E> extends Collection<E> {
//先自定义List接口，增加使用索引的方法
E remove(int index);
E set(int index,E e);
E get(int index);
}
class CustomizeOneWayLinkedList<E> implements CustomizeList<E>{
//自定义单向链表
private static final class Node<E> {
//结点 内部类
E item;
Node<E> next;
//单向链表只有直接后继结点一个指针
public Node(E item, Node<E> next) {
this.item = item;
this.next = next;
}
}
private Node<E> first;
private int size;
private void indexCheck(int index){
//执行需要索引的方法时都先进行索引检查
if (index<0||index>=size) throw new IndexOutOfBoundsException("index:"+index+" size:"+size);
//对现有结点进行操作时范围为[0,size)，执行插入操作时范围为[0,size]
}
private Node<E> getNode(int index){
Node<E> n = first;
for (int i = 0;i<index;i++){
n = n.next;
}
return n;
}
@Override
public E remove(int index) {
indexCheck(index);
//先进行索引检查，包括空容器index=0时也会报索引越界，所以能通过检查说明容器内有元素
Node<E> temp;
if (index==0){
//单向链表的删除结点是将前驱结点跳过当前结点链到后继结点上，所以先要判断是否存在前驱结点，单向链表没有prev属性，只能用index-1来调用，当index=0时-1会报错，所以要单独判断
temp = first;
first = first.next;
}else {
Node<E> prev = getNode(index-1);
temp = prev.next;
prev.next = temp.next;
}
//用temp缓存要删除的结点
E e = temp.item;
temp.item = null;
temp.next = null;
size--;
return e;
}
@Override
public E set(int index, E e) {
indexCheck(index);
Node<E> n = getNode(index);
E oldE = n.item;
n.item = e;
return oldE;
}
@Override
public E get(int index) {
indexCheck(index);
return getNode(index).item;
}
@Override
public int size() {
return size;
}
@Override
public boolean isEmpty() {
return size==0;
}
public int indexOf(Object o){
if (o==null)return -1;
Node<E> n = first;
for (int i = 0 ;i<size;i++,n = n.next){
//size=0时不执行循环
if (o.equals(n.item))return i;
}
return -1;
}
@Override
public boolean contains(Object o) {
return indexOf(o)!=-1;
}
@Override
public Iterator<E> iterator() {
return new Iterator<E>() {
//匿名内部类
int next = -1;
int cursor = 0;
@Override
public boolean hasNext() {
return cursor!=size;
}
@Override
public E next() {
next = cursor++;
return CustomizeOneWayLinkedList.this.get(next);
}
@Override
public void remove() {
CustomizeOneWayLinkedList.this.remove(next);
//外部类的remove方法中已经size--了
next = -1;
//将next变为-1，禁止连续删除
cursor--;
}
};
}
@Override
public Object[] toArray() {
Object[] o = new Object[size];
Node<E> n = first;
for (int i = 0;i<size;i++,n = n.next){
o[i] = n.item;
}
return o;
}
@Override
public <T> T[] toArray(T[] a) {
if (a.length<size) {
a = (T[]) Array.newInstance(a.getClass().getComponentType(), size);
//Array类的方法.newInstance(Class<T>,int)生成一个新的数组，数组类型为T[],将新数组作为Object对象返回，所以需要对返回值强转回T[]
//.getClass()返回对象的类的类对象Class<T[]> .getComponentType()返回数组类对象的组成成分/元素的类对象Class<T>
}
Node<E> n = first;
for (int i = 0; i < size; i++, n = n.next) {
a[i] = (T) n.item;
}
if (a.length>size){
a[size] = null;
}
return a;
}
@Override
public boolean add(E e) {
if (isEmpty()) {
first = new Node<>(e, null);
}else {
getNode(size-1).next = new Node<>(e,null);
//将结点链至表尾
}
size++;
return true;
}
@Override
public boolean remove(Object o) {
if (o==null)return false;
Node<E> p = null;
for (Node<E> m = first;m!=null;p=m,m=m.next){
//first==null时不执行循环
if (o.equals(m.item)){
if (p==null){
//当m为first时p还没有赋值，判断p==null即判断m==first
first=first.next;
}else {
p.next = m.next;
}
m.item=null;
m.next=null;
size--;
return true;
}
}
return false;
}
@Override
public boolean containsAll(Collection<?> c) {
if (c==null||c.isEmpty()||isEmpty())return false;
for (Object o :
c) {
if (!contains(o)) return false;
}
return true;
}
@Override
public boolean addAll(Collection<? extends E> c) {
//形参类型为Collection接口，只要元素同类或子类就可以使不同类型的容器取并集
if (c==null||c.isEmpty())return false;
Node<E> n;
Iterator<? extends E> itr = c.iterator();
//使用迭代器来添加
if (isEmpty()){
first = new Node<>(itr.next(),null);
n = first;
}else {
n = getNode(size-1);
//要调用size-1所以需要单独处理size=0的情况
}
while (itr.hasNext()){
n.next = new Node<>(itr.next(),null);
//将元素从原容器中取出封入新的结点中添加至表尾
n = n.next;
}
size += c.size();
return true;
}
@Override
public boolean removeAll(Collection<?> c) {
if (c == null||c.isEmpty()||isEmpty())return false;
boolean modified = false;
for (Object o :
c) {
while (remove(o)) {
//remove()方法中已经将size--了，这里不需要再次修改size
modified = true;
}
}
return modified;
}
@Override
public boolean retainAll(Collection<?> c) {
if (c==null||c.isEmpty()||isEmpty())return false;
boolean modified = false;
for (Iterator<E> it = iterator();it.hasNext();){
if (!c.contains(it.next())) {
it.remove();
modified = true;
}
}
return modified;
}
@Override
public void clear() {
for (Node<E> n = first;first!=null;n =first){
first = first.next;
n.item = null;
n.next = null;
}
size =0;
}
@Override
public String toString() {
if (isEmpty())return "[]";
StringBuilder str = new StringBuilder("[");
for (Node<E> n = first;;){
//循环条件空着为死循环，迭代因子放在语句内
str.append(n.item);
n=n.next;
if (n==null){
return str.append("]").toString();
}
str.append(", ");
}
}
//单向链表实现栈容器方法
public boolean empty(){
return first==null;
}
public E pop(){
if (empty()){
return null;
}
Node<E> n = first;
first = first.next;
E e = n.item;
n.item = null;
n.next = null;
size--;
return e;
}
public E peek(){
return empty()?null:first.item;
}
public void push(E e){
first = new Node<>(e,first);
size++;
}
public int search(E e){
if (empty()||e==null)return -1;
int i = 1;
for (Node<E> n = first;n!=null;n = n.next){
if (e.equals(n.item))return i;
i++;
}
return -1;
}
public static void main(String[] args) {
CustomizeOneWayLinkedList<String> ll1 = new CustomizeOneWayLinkedList<>();
CustomizeOneWayLinkedList<String> ll2 = new CustomizeOneWayLinkedList<>();
//测试略
}
}
