单链表的增删改查(带头节点)
程序员文章站
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;
}
}
}
}
上一篇: 带头循环双链表
下一篇: leetcode 第73题 矩阵转置