package LinkList;
public class Node {
public T data;//数据域
public Node next;//结点域
//默认构造方法
public Node(){
}
//带参构造方法,非头结点初始化
public Node(T data,Node next){
this.data=data;
this.next=next;
}
//头结点初始化
public Node(Node next){
this.next=next;
}
//显示结点值
public void display(){
System.out.print(data+" ");
}
}
************************************************华丽的分割线************************************************************************
package LinkList;
/**
* ****************带头结点的单链表及其实现*********************
*
* @author wl
*
*/
public class SinglyLinkList {
Node head;//头结点
int size;//链表大小
Node current;//当前结点
//初始化一个空链表
public SinglyLinkList(){
this.head=new Node(null);
this.size=0;
this.current=head;
}
//判断链表是否为空
public boolean isEmpty(){
return size==0;
}
//打印链表
public void traverse(){
if(isEmpty()){
System.out.println("null");
}else{
for(Node p=head.next;p!=null;p=p.next){
System.out.print(p.data+",");
}
System.out.println();
}
}
//从头结点增加结点
public void addFromHead(T value){
Node node=new Node(value,null);
node.next=head.next;
head.next=node;
size++;
}
//从尾结点增加结点
public void addFromTail(T value){
Node node=new Node(value,null);
this.current=head.next;
if(current==null){
head.next=node;
size++;
}else{
while(current.next!=null){//将当前结点定位到尾结点
current=current.next;
}
current.next=node;
size++;
}
}
//从头结点删除
public void removeFromHead(){
if(isEmpty()){//判断链表是否为空
throw new RuntimeException("链表为空");
}
current=head.next;//当前结点
head.next=current.next;
current.next=null;
size--;
}
//从尾结点删除
public void removeFromTail(){
if(isEmpty()){//判断链表是否为空
throw new RuntimeException("链表为空");
}
Node prev=null;//前一个结点
this.current=head.next;
while(current.next!=null){//将当前结点定位到尾结点
prev=current;
current=current.next;
}
prev.next=null;
size--;
}
//在第index后面插入一个结点
public void insert(int index,T value){
if(index<0||index>size){
throw new RuntimeException("参数index有误");
}
Node node=new Node(value,null);
if(index==0){
node.next=head.next;
head.next=node;
size++;
}else{
int count=0;//计数器
Node prev=null;//前一个结点
current=head.next;
while(current!=null&&count!=index){//将当前结点定位到第index个结点处
prev=current;
current=current.next;
count++;
}
node.next=current;
prev.next=node;
size++;
}
}
//删除任意位置index位置的某个结点
public void remove(int index){
if(index<0||index>size){
throw new RuntimeException("参数index有误");
}
if(index==0){
current=head.next;
head.next=current.next;
size--;
}else{
int count=0;//计数器
Node prev=null;//前一个结点
current=head.next;
while(current!=null&&count!=index){//将当前结点定位到第index个结点处
prev=current;
current=current.next;
count++;
}
prev.next=current.next;
current=null;
size--;
}
}
//根据value值删除结点，当有多个相同的value值时，只删除第一个
public void removeByValue(T value){
if(isEmpty()){
throw new RuntimeException("链表为空");
}
int count=0;//计数器
Node prev=null;//前一个结点
current=head.next;
while(current!=null&¤t.data!=value){//将当前结点定位到值为value的第一个结点处
prev=current;
current=current.next;
count++;
}
if(count>size){
throw new RuntimeException("不存在值为value的结点");
}
prev.next=current.next;
current=null;
size--;
}
}
