节点类
除双向链表外的节点类
/*
* 节点类
* params:指向下一个节点的成员变量
* 其他的成员变量
*/
public class Link {
public int num;
public Link next;
public Link(int num){
this.num=num;
}
}
双向链表的节点类
/*
* 双向链表的节点类
*/
public class Link {
public int num;
public Link next;
public Link previous;
public Link(int num){
this.num=num;
}
}
单链表
每个节点只指向下一个节点
单链表的操作类
/*
* 单链表的操作类
*/
public class SingleList {
//头节点
public Link first;
//在链表的头部插入一个元素
public void insertFirst(int num){
Link link=new Link(num);
link.next=first;
first=link;
}
//在链表的头部删除一个元素
public Link deleteFirst(){
if(first==null){
return null;
}
Link temp=first;
first=first.next;
return temp;
}
//遍历显示链表中的所有元素
public void display(){
Link current=first;
while(current!=null){
System.out.println(current.num+",");
current=current.next;
}
}
//根据变量查询指定元素节点
public Link find(int num){
Link current=first;
while(current.num!=num){
if(current.next==null){
return null;
}else{
current=current.next;
}
}
return current;
}
//根据指定变量删除节点
public Link delete(int num){
Link current=first;
Link previous=null;
while(current.num!=num){
if(current.next==null){
return null;
}else{
previous=current;
current=current.next;
}
}
if(current==first){
first=first.next;
}else{
previous.next=current.next;
}
return current;
}
}
双端链表
每个节点指向下一个节点，在链表的操作类中同时保留着对头结点和尾节点的引用
/*
* 双端链表的操作类
*/
public class FirstLastList {
public Link first;
public Link last;
//在头部插入一个节点
public void insertFirst(int num){
Link link=new Link(num);
if(first==null){
last=link;
}
link.next=first;
first=link;
}
//在尾部插入一个节点
public void insertLast(int num){
Link link=new Link(num);
if(first==null){
first=link;
}else{
last.next=link;
}
last=link;
}
//在头部删除一个节点
public Link deleteFirst(){
if(first==null){
return null;
}
Link temp=first;
//判断删除这个节点后是否没有节点了,如果没有节点要把last置为null
if(first.next==null){
last=null;
}
first=first.next;
return temp;
}
//遍历显示节点
public void display(){
Link current=first;
while(current!=null){
System.out.println(current.num);
current=current.next;
}
}
}
1.双端链表不能直接从尾部删除元素，因为无法直接找到尾部前一个节点的引用。
2.双端链表按元素查找和删除节点的操作和单链表相同。
双向链表
1 双向链表，每一个节点即指向前一个节点，同时又指向下一个节点。
2 双向链表可以是双端链表也可以不是双端链表。
/*
* 双向链表的操作类
*/
public class DoubleLinkList {
public Link first;
public Link last;
//在头部插入一个节点
public void insertFirst(int num){
Link newLink=new Link(num);
if(first==null){
last=newLink;
}else{
first.previous=newLink;
}
newLink.next=first;
first=newLink;
}
//在尾部插入一个节点
public void insertLast(int num){
Link newLink=new Link(num);
if(first==null){
first=newLink;
}else{
last.next=newLink;
newLink.previous=last;
}
last=newLink;
}
//在某一个节点后面插入一个节点
public void insertAfter(int num,int targetNum){
Link target=new Link(targetNum);
Link current=find(num);
if(current==null)
return;
if (current==last) {
current.next=target;
target.previous=current;
last=target;
}else{
target.next=current.next;
current.next.previous=target;
current.next=target;
target.previous=current;
}
}
//删除第一个节点
public Link deleteFirst(){
if(first==null)
return null;
if(first.next==null){
last=null;
}else{
first.next.previous=null;
}
Link temp=first;
first=first.next;
return temp;
}
//删除最后一个节点
public Link deleteLast(){
if(last==null){
return null;
}
Link temp=last;
if(last.previous==null){
first=null;
}else{
last.previous.next=null;
}
last=last.previous;
return temp;
}
//查询某一个节点
public Link find(int num){
Link current=first;
while(current.num!=num){
if(current.next==null){
return null;
}
current=current.next;
}
return current;
}
//删除某一个节点
public Link delete(int num){
Link current=first;
while(current.num!=num){
if(current.next==null){
return null;
}
current=current.next;
}
if(current==first){
first.next.previous=null;
first=current.next;
}else if(current==last){
current.previous.next=null;
last=current.previous;
}
else{
current.previous.next=current.next;
current.next.previous=current.previous;
}
return current;
}
//从前向后遍历所有节点
public void displayForward(){
Link current=first;
while(current!=null){
System.out.println(current.num);
current=current.next;
}
}
//从后向前遍历所有节点
public void displayBackword(){
Link current=last;
while(current!=null){
System.out.println(current.num);
current=current.previous;
}
}
}
有序链表
/*
* 有序链表操作类
*/
public class SortedList {
public Link first;
//按从小到大的顺序向链表中插入元素
public void insert(int num){
Link link=new Link(num);
Link current=first;
Link previous=null;
while(current!=null&&num>current.num){
previous=current;
current=current.next;
}
//previous==null说明没进循环，first为null或者插入的元素是目前最小的
if(previous==null){
first=link;
}else{
previous.next=link;
}
link.next=current;
}
}
有序链表除了插入操作外，其他操作和单链表一致。
