Java--不带头节点的单链表、循环单链表

①不带头节点的单链表

public class Link<T> { private class Entry<E>{ private E value; private Entry<E> next; public Entry(E value){ this.value = value; } } private Entry<T> headEntry; private Entry<T> tailEntry; public Link(){ } //头插 public void addHead(T value){ Entry<T> newEntry = new Entry<>(value); if(headEntry == null){ headEntry = newEntry; tailEntry = newEntry; }else{ newEntry.next = headEntry; headEntry = newEntry;//新头 } } //尾插 public void addTail(T value){ Entry<T> newEntry = new Entry<>(value); if(headEntry == null){ headEntry = newEntry; tailEntry = newEntry; }else{ tailEntry.next = newEntry; tailEntry = newEntry;//更新新尾 } } //头删 public void deleteHead(){ if(headEntry == null){ headEntry = null; tailEntry = null; } Entry<T> p = headEntry; headEntry = headEntry.next; p.value = null; p.next = null; } //尾删 public void deleteTail() { Entry<T> pre = searchPre(); if (pre == null) { return; } if (headEntry.next == null) { headEntry.value = null; headEntry = null; tailEntry = null; } else { pre.next = null; tailEntry.value = null; tailEntry = pre; } } //用来寻找尾巴前驱 private Entry<T> searchPre(){ for(Entry<T> p = headEntry;p!=null;p=p.next){ if(p.next == tailEntry){ return p; } } return null; } public void show() { for(Entry<T> p = headEntry;p!=null;p=p.next){ System.out.print(p.value +" "); } System.out.println(); } //测试 public static void main(String[] args) { Link<Integer> link=new Link<>(); link.addHead(1); link.addHead(2); link.addHead(3); link.addTail(4); link.addTail(5); link.deleteHead(); link.deleteTail(); link.show(); } }

②不带头节点的循环单链表

public class SingleList<T> { private static class Entry<E>{ private Entry<E> next; private E value; public Entry(E value){ this.value = value; next = this; //循环 } } private Entry<T> headEntry; private Entry<T> tailEntry; public SingleList(){ } public void addHead(T value){ Entry<T> newEntry = new Entry<>(value); if(headEntry == null){ headEntry = newEntry; tailEntry = newEntry; }else{ //插入的这个元素后一个即原来的头 newEntry.next = headEntry; //更新头 headEntry = newEntry; //尾部下一个指向现在的头 tailEntry.next = headEntry; } } public void addTail(T value){ Entry<T> newEntry = new Entry<>(value); if(headEntry == null){ headEntry = newEntry; tailEntry = newEntry; }else { tailEntry.next = newEntry; newEntry.next = headEntry; tailEntry = newEntry; } } public void deleteHead(){ if(headEntry == null) //空链表 return; headEntry.value = null; if(headEntry.next == headEntry){ //只有一个节点 headEntry = null; tailEntry = null; }else { tailEntry.next = headEntry.next; headEntry = headEntry.next; //更新头 } } private Entry<T> searchPre(){ Entry<T> p = headEntry; do{ if(p.next == tailEntry){ return p; } p=p.next; }while(p!=headEntry); //此处使用do while比较简单，for循环条件出错容易陷入死循环 return null; } public void deleteTail(){ if(headEntry == null){ return; } if(headEntry.next == headEntry){ headEntry = null; tailEntry = null; }else { Entry<T> pre = searchPre(); pre.next = tailEntry.next; tailEntry.value = null; tailEntry = pre;//更新尾 } } public void show(){ if(headEntry == null){ return; } Entry<T> p = headEntry; do{ System.out.print(p.value+" "); p=p.next; }while(p!=headEntry); } public static void main(String[] args) { SingleList<Integer> singleList = new SingleList<>(); singleList.addHead(1); singleList.addHead(2); singleList.addHead(3); singleList.addTail(4); singleList.addTail(5); singleList.deleteHead(); singleList.deleteTail(); singleList.show(); } }