链表的java实现

      使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。

 

        链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）。

链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。

而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

package com.algorithm;

/**
 * 链表的链结点，相当于车厢
 * @author lenovo
 *
 */
public class Node {

	/**
	 * 数据域
	 */
	public long data;
	
	//结点域(指针域)，相当于火车与火车的链接
	public Node next;
	
	public Node(long value){
		this.data =value;
	}
	
	/**
	 * 显示方法
	 */
	public void display(){
		System.out.print(data+" ");
	}
}

 

 

package com.algorithm;

/**
 * 链表，相当于火车头
 * @author lenovo
 *使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。
 *但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。
 *在计算机科学中，链表作为一种基础的数据结构可以用来生成其它类型的数据结构。
 *
 *链表通常由一连串节点组成，每个节点包含任意的实例数据（data fields）和一或两个用来指向上一个/或下一个节点的位置的链接（"links"）。
 *链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。
 *而链表是一种自我指示数据类型，因为它包含指向另一个相同类型的数据的指针（链接）。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。
 */
public class LinkList {

	/**
	 * 头结点，相当于火车头
	 */
	private Node first;
	
	public LinkList(){
		first =null;
	}
	
	/**
	 * 插入一个结点，在头结点插入
	 */
	public void insertFirst(long value){
		Node node = new Node(value);
		node.next = first;
		first =node;
	}
	
	/**
	 * 删除一个结点，在头结点删除
	 */
	public Node deleteFirst(){
		Node node = first;
		first=node.next;
		return node;
	}
	
	/**
	 * 显示方法
	 */
	public void display(){
		Node current = first;
		
		while(current!=null){
			current.display();
			current = current.next;
		}
		System.out.println();
	}
	
	/**
	 * 查找方法
	 * @param value
	 * @return
	 */
	public Node find(long value){
		Node current = first;
		while(current.data!=value){
			if(current.next==null){
				return null;
			}
			current = current.next;
		}
		return current;
	}
	
	/**
	 * 删除方法，根据数据域删除
	 * @param value
	 * @return
	 */
	public Node delete(long value){
		Node current = first;
		Node previous =first; //当前元素
		while(current.data!=value){
			if(current.next==null){
				return null;
			}
			previous=current;
			current = current.next;
			
		}
		if(current == first) {
			first = first.next;
		} else {
			previous.next = current.next;
		}
		return current;
	}
	
	public static void main(String[] args) {
		LinkList linkList = new LinkList();
		linkList.insertFirst(34);
		linkList.insertFirst(23);
		linkList.insertFirst(12);
		
		linkList.display();
		
		linkList.deleteFirst();
		linkList.display();
		
		Node node = linkList.find(34);
		node.display();
		
		System.out.println("--------");
		 node = linkList.delete(34);
		 node.display();
		 
		 System.out.println("~~~~~~~~~~~~~~~~~~~~~~");
		 linkList.display();
	}
}