队列：链表

Bertha 。 2021-11-04 14:00 299阅读 0赞

#### 什么是单链表： ####

由一串对象连接起来形成的表

#### 单链表 ####

1.  创建一个节点类Node.class
2.  存放所需要的属性数据和next(下一个对象)
3.  创建一个节点管理器来连接和管理节点ManageNode.class
4.  该管理器中初始化一个头节点不存放任何数据
5.  增加添加节点、修改节点、删除节点、打印节点的方法

##### code #####

package com.lemon.singlelinklist;
    
    //管理节点
    public class SingleLinkListManage {
        
    	private Node headNode = new Node(0, "");
    
    	// 添加数据
    	public void addNode(Node node) {
        
    		Node temp = headNode;
    		while (true) {
        
    			if (temp.next == null) {
        
    				break;
    			}
    			temp = temp.next;
    		}
    		temp.next = node;
    	}
    
    	//有序添加
    	public void orderAddNode(Node node) {
        
    		Node temp = headNode;
    		boolean flag = true;
    		while(true) {
        
    			if(temp.next == null) {
        
    				break;
    			}
    			if(temp.next.id > node.id) {
        
    				if(temp.next.id == node.id) {
        
    					flag = false;
    				}
    				break;
    			}
    			temp = temp.next;
    		}
    		if(flag) {
        
    			node.next = temp.next;
    			temp.next = node;
    		}
    	}
    	
    	// 打印数据
    	public void printSingleLinkList() {
        
    		Node temp = headNode;
    		if (temp.next == null) {
        
    			System.err.println("链表为空");
    		}
    		temp = temp.next;
    		while (true) {
        
    			if (temp == null) {
        
    				break;
    			}
    			System.out.println(temp.id + "\t" + temp.name);
    			temp = temp.next;
    		}
    	}
    	
    	//修改数据
    	public void reviseNodeName(Node node) {
        
    		Node temp = headNode.next;
    		while(true) {
        
    			if(temp == null) {
        
    				break;
    			}
    			if(temp.id == node.id) {
        
    				temp.name = node.name;
    				break;
    			}
    			temp = temp.next;
    		}
    	}
    	
    	//删除数据
    	public void deleteNode(int id) {
        
    		Node temp = headNode;
    		while(true) {
        
    			if(temp == null) {
        
    				break;
    			}
    			if(temp.next.id == id) {
        
    				temp.next = temp.next.next;
    				break;
    			}
    			temp = temp.next;
    		}
    	}
    }
    //节点
    class Node {
        
    	int id;
    	String name;
    	Node next;
    
    	public Node(int id, String name) {
        
    		this.id = id;
    		this.name = name;
    		next = null;
    	}
    
    	@Override
    	public String toString() {
        
    		return "Node [id=" + id + ", name=" + name + "]";
    	}
    }

package com.lemon.singlelinklist;
    
    public class Test01 {
        
    	public static void main(String[] args) {
        
    		Node node1 = new Node(1, "q");
    		Node node2 = new Node(2, "w");
    		Node node3 = new Node(3, "e");
    		
    		SingleLinkListManage manage = new SingleLinkListManage();
    		manage.addNode(node1);
    		manage.addNode(node3);
    		manage.addNode(node2);
    		
    		manage.printSingleLinkList();
    	}
    }

##### 关于单链表的面试题 #####

1.  求单链表中有效节点的个数

1.  查找单链表中的倒数第k个节点

package com.lemon.singlelinklist;
    
    public class Test02 {
        
    	public static void main(String[] args) {
        
    		Node node1 = new Node(1, "q");
    		Node node2 = new Node(2, "w");
    		Node node3 = new Node(3, "e");
    		Node node4 = new Node(4, "f");
    		
    		SingleLinkListManage manage = new SingleLinkListManage();
    		manage.addNode(node1);
    		manage.addNode(node2);
    		manage.addNode(node3);
    		manage.addNode(node4);
    		System.out.println(getLength(manage.headNode));
    		System.out.println(getNode(3, manage));
    	}
    	
    	public static int getLength(Node node) {
        
    		if(node.next == null) {
        
    			return 0;
    		}
    		int length = 0;
    		while(node.next != null) {
        
    			length++;
    			node = node.next;
    		}
    		return length;
    	}
    	
    	public static int getNode(int k, SingleLinkListManage manage) {
        
    		int n = getLength(manage.headNode);
    		int i = n - k;
    		Node temp = manage.headNode.next;
    		if(i > 0) {
        
    			while(true) {
        
    				if(i > 0) {
        
    					temp = temp.next;
    					i--;
    				}
    				return temp.id;
    			}
    		}
    		return -1;
    	}
    }

#### 双向链表 ####

##### code #####

package com.lemon.doublelinkedlist;
    
    public class DoubleLinkList {
        
    	private Node headNode = new Node(0);
    	
    	//添加数据
    	public void add(int value) {
        
    		Node temp1 = headNode;
    		Node temp2 = headNode;
    		
    		while(temp1.next != null) {
        
    			temp2 = temp1;
    			temp1 = temp1.next;
    		}
    		
    		temp1.next = new Node(value);
    		temp1.pre = temp2;	
    	}
    	
    	//删除数据
    	public void delete(int index) {
        
    		Node temp = headNode;
    		if(isEmpty()) {
        
    			return;
    		}
    		for(int i = 0; i < index; i++) {
        
    			temp = temp.next;
    		}
    		temp.pre.next = temp.next;
    		temp.next.pre = temp.pre;
    	}
    	
    	//修改数据
    	public void revise(int index, int value) {
        
    		Node temp = headNode;
    		if(isEmpty()) {
        
    			return;
    		}
    		for(int i = 0; i < index; i++) {
        
    			temp = temp.next;
    		}
    		temp.val = value;
    	}
    	
    	
    	//判断数据是否为空
    	public boolean isEmpty() {
        
    		if(headNode.pre == headNode.next) {
        
    			return true;
    		}
    		return false;
    	}
    	
    	//打印
    	public void print() {
        
    		Node temp = headNode.next;
    		while(temp != null) {
        
    			System.out.println(temp.toString());
    			temp = temp.next;
    		}
    	}
    }
    
    class Node {
        
    	public int val;
    	public Node pre;
    	public Node next;
    	
    	public Node(int val) {
        
    		this.val = val;
    	}
    
    	@Override
    	public String toString() {
        
    		return "Node [val=" + val +"]";
    	}	
    }