欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

单链表的增删改查(带头节点)

程序员文章站 2022-03-15 20:33:20
...

带头节点 的单链表:在初始化时产生一个headEntry结点,其value域和next域均为空。其链表结构如下:
单链表的增删改查(带头节点)
注意:带头节点和不带头节点的单链表区别就在headEntry

带头节点的单链表我们需要从headEntry的下个节点开始进行各种操作,而不带头节点的从headEntry开始操作,操作方法大同小异,适当分析,搞清楚起始点即可

  • Entry类封装节点属性,包括value域及next域
  • 代码实现如下:
public class Entry<E extends Comparable<E>> {
    private E value;
    private Entry next;
    public Entry(){
    }
    public Entry(E value){
        this.value=value;
    }
    public void setValue(E value) {
        this.value = value;
    }
    public void setNext(Entry next) {
        this.next = next;
    }
    public E getValue() {
        return value;
    }
    public Entry getNext() {
        return next;
    }
}
  • Link类封装头插尾插头删尾删等操作
  • 代码实现如下:
public class Link<T extends Comparable<T>> {
    private Entry<T> headEntry;
    private Entry<T> tailEntry;
    public Link(){         //初始化headEntry节点
        headEntry=new Entry<>();
    }
    
    //头插
    public void addHead(T value){
        Entry<T> newEntry=new Entry<>(value);
        if(headEntry.getNext()==null){
            headEntry.setNext(newEntry);
            tailEntry=newEntry;
        }
        newEntry.setNext(headEntry.getNext());
        headEntry.setNext(newEntry);//更新头节点
    }
    
    //尾插
    public void addTail(T value){
        Entry<T> newEntry=new Entry<>(value);
        if(headEntry.getNext()==null){
            headEntry.setNext(newEntry);
            tailEntry=newEntry;
        }
        tailEntry.setNext(newEntry);
        tailEntry=newEntry;//更新尾节点
    }
    
    //头删
    public void deleteHead(){
        if(headEntry.getNext()==null){
            return;
        }
        Entry p=headEntry.getNext();
        p.setValue(null);//防止内存泄漏
        headEntry.setNext(headEntry.getNext().getNext());
    }
    
    //尾删
    public void deleteTail(){
        if(headEntry.getNext()==null){
            return;
        }
        Entry<T> p=headEntry.getNext();
        for(;p.getNext().getNext().getNext()!=null;p=p.getNext()){
            ;   //找尾部前驱p
        }
        p.getNext().setNext(null);
        tailEntry=p.getNext();
    }
    
    //删除指定节点
    public void deleteValue(T value){
        if(headEntry.getNext()==null){
            return;
        }
        if(headEntry.getNext().getValue().compareTo(value)==0){
            deleteHead();
            if(headEntry==tailEntry) {
                tailEntry.setNext(null);
            }
            return;
        }
        if(tailEntry.getValue().compareTo(value)==0){
            deleteTail();
            if(headEntry==tailEntry) {
                tailEntry.setNext(null);
            }
            return;
        }
        for(Entry<T> p=headEntry.getNext();p.getNext().getNext()!=null;p=p.getNext()){
            if(p.getNext().getValue().compareTo(value)==0){
                p.getNext().setValue(null);
                p.setNext(p.getNext().getNext());
                break;
            }
        }
    }
}
相关标签: 带头节点