单链表

叁歲伎倆 2021-08-11 21:03 512阅读 0赞

【一】单链表特点

> 1.存储方式为：节点，节点包含data域和next域，data域用于存储数据，next域用于存储下一个节点对应的地址。  
> 2.链表的各个节点不一定是连续存储的。  
> 3.链表分为带头结点的链表和没有头结点的链表。

【二】单链表的功能实现

> 功能列表：
> 
> 1.添加节点  
> 2.插入节点  
> 3.修改节点  
> 4.删除节点  
> 5.遍历元素  
> 6.返回倒数第K个节点获取到单链表中的节点个数，不统计头结点  
> 7.单链表的反转（思想：创建一个新的链表，遍历旧链表，每遍历一个节点，插入在头结点之后）  
> 8.逆序打印单链表（方式一：先反转再遍历（破坏了链表结构，不建议）；方式二：利用栈的先进后出）

import java.util.Stack;
    
    public class LinkedListInf {
    	public static void main(String[] args) {
    		
    		System.out.println("------添加节点------");
    		SingleLinkedList sll=new SingleLinkedList();
    		sll.addNode(new StudentNode(1,"杨玉环","第一美女"));
    		sll.addNode(new StudentNode(2,"西施","第二美女"));
    		sll.addNode(new StudentNode(3,"貂蝉","第三美女"));
    		sll.addNode(new StudentNode(4,"王昭君","第四美女"));
    		sll.list();
    		System.out.println("单链表的逆序打印");
    		sll.reversePrint();
    		System.out.println("单链表的反转");
    		sll.reverseLinkedList();
    		sll.list();
    		/*System.out.println("------插入节点------");
    		SingleLinkedList sll2=new SingleLinkedList();
    		sll2.addNodeByOrder(new StudentNode(102,"张三","西安"));
    		sll2.addNodeByOrder(new StudentNode(104,"王五","深圳"));
    		sll2.addNodeByOrder(new StudentNode(108,"孙七","北京"));
    		sll2.addNodeByOrder(new StudentNode(101,"李四","咸阳"));
    		sll2.addNodeByOrder(new StudentNode(101,"李四","咸阳"));
    		
    		System.out.println("--修改前");
    		sll2.list();
    		sll2.updateNode(new StudentNode(104,"王小二","北京"));
    		System.out.println("--修改后");
    		sll2.list();
    		System.out.println("--删除节点id为101和1010后");
    		sll2.deleteNode(new StudentNode(101,"李四","咸阳"));
    		sll2.deleteNode(new StudentNode(1010,"李__","~~"));
    		sll2.list();
    		
    		int count=sll2.countNode();
    		System.out.println("该链表的有效节点数为"+count);
    		
    		StudentNode node=sll2.getIndexNode(2);
    		System.out.println("倒数第2个节点为："+node);
    		
    		StudentNode node2=sll2.getIndexNode(4);
    		System.out.println("倒数第4个节点为："+node2);*/
    		
    		
    	}
    }
    class SingleLinkedList{
    	//先初始化一个头结点
    	private StudentNode head=new StudentNode(0,"","");
    	
    	//使用栈的方式，逆序打印单链表
    	public void reversePrint() {
    		Stack<StudentNode> stack=new Stack<>();
    		if(head.next==null) {
    			return;
    		}
    		StudentNode temp=head.next;
    		while(temp!=null) {
    			stack.add(temp);
    			temp=temp.next;
    		}
    		while(stack.size()>0) {
    			System.out.println(stack.pop());
    		}
    		
    	}
    	//添加节点
    	public void addNode(StudentNode node) {
    		StudentNode temp=head;
    		while(true) {
    			
    			if(temp.next==null) {
    				break;
    			}
    			temp=temp.next;
    		}
    		temp.next=node;
    	}
    	//插入节点
    	public void addNodeByOrder(StudentNode node) {
    		StudentNode temp=head;
    		boolean flag=false;
    		while(true) {
    			if(temp.next==null) {
    				break;
    			}else if(temp.next.id>node.id) {
    				break;
    			}else if(temp.next.id==node.id){
    				flag=true;
    				break;
    			}
    			temp=temp.next;
    		}
    		if(flag) {
    			System.out.printf("序号为%d的同学已经位于链表中\n",node.id);
    			return;
    		}
    		node.next=temp.next;
    		temp.next=node;
    	}
    	//修改节点
    	public void updateNode(StudentNode node) {
    		StudentNode temp=head;
    		boolean flag=false;
    		while(true) {
    			if(temp.next==null) {
    				break;
    			}else if(temp.id==node.id){
    				flag=true;
    				break;
    			}
    			temp=temp.next;
    		}
    		if(flag) {
    			temp.name=node.name;
    			temp.adress=node.adress;
    		}else {
    			System.out.printf("没有%d找到要修改的数据\n",node.id);
    			
    		}
    	}
    	
    	//删除节点
    	public void deleteNode(StudentNode node) {
    		StudentNode temp=head;
    		boolean flag=false;
    		while(true) {
    			if(temp.next==null) {
    				
    				break;
    			}else if(temp.next.id==node.id){
    				flag=true;
    				break;
    			}
    			temp=temp.next;
    		}
    		if(flag) {
    			temp.next=temp.next.next;
    		}else {
    			System.out.printf("要删除的节点%d不存在\n",node.id);
    		}
    	}
    	//遍历元素
    	public void list() {
    		StudentNode temp=head;
    		while(true) {
    			if(temp.next==null) {
    				return;
    			}
    			temp=temp.next;
    			System.out.println(temp);
    			
    		}
    	}
    	
    	//返回倒数第K个节点
    	public StudentNode getIndexNode(int index) {
    		StudentNode temp=head.next;
    		if(temp==null) {
    			return null;
    		}
    		int length=countNode();
    		if(index<0||index>length) {
    			return null;
    		}
    		for(int i=0;i<length-index;i++) {
    			temp=temp.next;
    		}
    		return temp;
    	}
    	
    	//单链表的反转
    	public void reverseLinkedList() {
    		StudentNode reverseHead=new StudentNode(0,"","");//创建一个新的链表
    		StudentNode next=null;
    		StudentNode temp=head.next;
    		if(temp==null||temp.next==null) {
    			return;
    		}
    		while(temp!=null) {
    			next=temp.next;
    			temp.next=reverseHead.next;
    			reverseHead.next=temp;
    			temp=next;
    		}
    		head.next=reverseHead.next;
    	}
    	//获取到单链表中的节点个数，不统计头结点
    	public int countNode() {
    		StudentNode temp=head.next;
    		int count = 0;
    		if(temp==null) {
    			return 0;
    		}
    		
    		while(temp!=null) {
    			count++;
    			temp=temp.next;
    			//System.out.println(temp);
    		}
    		return count;
    	}
    }
    
    class StudentNode{
    	public int id;
    	public String name;
    	public String adress;
    	public StudentNode next;
    	StudentNode(int id,String name,String adress){
    		this.id=id;
    		this.name=name;
    		this.adress=adress;
    	}
    	@Override
    	public String toString() {
    		return "StudentNode [id=" + id + ", name=" + name + ", adress=" + adress +  "]";
    	}
    }

【特别说明】因为示例比较多，这里不做截图