单向链表知识

单向链表

• 对于单向链表来说，任何一个节点Node中都有两个属性：存储数据和下一个节点的内存

• 链表优点：随机删除元素效率高【因为增删元素不涉及到大量元素位移】

• 链表缺点：查询效率较低，每一次查找

  package chapter1;
  public class Node {
  	
  	//存储数据
  	Object data;
  	
  	//下一个节点的内存地址
  	Node next;
  	
  	public Node() {
  		
  	}
  	
  	public Node(Object data,Node next) {
  		this.data = data;
  		this.next = next;
  	}
  	
  }
  
  package chapter1;
  import chapter1.Node;
  public class Link {
  	
  	Node header = null;
  	
  	int size = 0;
  	
  	public int size() {
  		return size;
  	}
  	
  	//添加元素的方法
  	public void add(Object data) {
  		//创建一个新的节点对象
  		//让之前单链表的末尾节点next指向新的节点对象
  		//有可能这个元素是第一个，也可能是第二个、第三个
  		if(header == null) {
  			//说明还没有节点
  			//new一个新的节点对象，作为节点对象
  			//这个时候的头节点既是一个头节点，又是一个末尾节点
  			header = new Node(data, null);
  		}
  		else {
  			//说明头不是空，头节点已经有了
  			//找出当前末尾节点，让当前末尾节点的next是新节点
  			Node currentLastNode = findLast(header);
  			currentLastNode.next = new  Node(data,null);
  			//末尾节点等于一个新的节点
  			size++;
  			
  		}
  		
  	}
  	
  	//专门查找末尾节点的方法
  	private Node findLast(Node node) {
  		if(node.next == null) {
  			//如果一个节点的next是null，说明这个节点就是末尾节点
  			return node;
  		}
  		//程序能够到这里说明：node不是末尾节点
  		return findLast(node.next);//递归算法
  	}
  	
  	//删除
  	public void remove(Object obj) {
  		//把要删的数据的内存地址给上一个数据的内存地址
  		
  	}
  	
  	//修改
  	public void modify(Object newObj) {
  		
  	}
  	
  	//查找
  	public int find(Object obj) {
  		return 1;
  	}
  	
  	//输出
  	public int P
  }
  
  import chapter1.Link;
  import chapter1.Node;
  public class Test02 {
  	public static void main(String[] args) {
  		//创建了一个集合对象
  		Link link = new Link();
  		
  		//在集合中添加元素
  		link.add(100);
  		link.add(200);
  		link.add(300);
  		
  		//获取元素
  		System.out.println(link.size());
  		
  	}
  }

  某个元素的时候都需要从头节点开始往下遍历