链表——初识链表

链表——前言：

 

（小弟初学数据结构，有错误的地方望大家不吝赐教）

 

 

认识链表：

列表相比数组更具有优势，链表不同于数据和其他数据结构依靠位置来进行访问或者其他操作，
如数组是依靠下表来操作数据。而链表是通过关系来寻找或者操作数据。

 

链表是由“链接点” 组成，每个链接点是一个数据对象，每个链接点的对象中包含着下一个链接点的引用（next），
但是链表本身有一个字段是指向第一个链接点的引用的。

 

链表的特性：

 

插入 和 删除 效率高，只需要变更指向的链接点即可。但是随即访问操作的效率很低，
由于链表是通过关系来确定数据的位置，所以，访问某个数据时，必须通过大量的链接点关系，才能访问到。
效率很低。

 

 

 

 

//链表
class LinkList{
	
	public static void main(String[] args) {
		LinkList l = new LinkList();
		//增加
		l.insertFirst(1,1d);
		l.insertFirst(2,2d);
		l.insertFirst(3,3d);
		l.displayList();
		//查询
		Link findLink = l.find(6);
		if(findLink != null){
			System.out.println(findLink.dData);
		}
		//删除
		l.deleteLike(7);
		l.displayList();
		
	}
	//第一个链接点的位置。
	public Link first;
	
	
	public LinkList(){
		first = null;
	}
	//插入数据：插入的新数据为链表的收割链接点，并且将下一个链接点的地址指向插入前的首数据。
	public void insertFirst(int id, double dd){
		//新链接点
		Link link = new Link(id,dd);
		//将新链接点的关系子段 next 指向旧的首链接点。
		link.next = first;
		//将链表的第一个链接点指向新增的链接点地址。
		first = link;
	}
	
	//删除：将当前first 指向第二个链接点断开和第一个链接点的连接，
	public Link deleteFirst(){
		Link temp = first;
		first = first.next;
		return first;
	}
	
	//查询
	public Link find(int key){
		//将link 
		Link current = first;
		//如果当前link 不是要查询的 数据，则通过它next 子段，查询到下一个链接点。
		//直到找到为止
		while(current.iData != key){
			if(current.next != null){
				//如果不是要查询的数据，则通过关系访问下一个链接点，
				//注意，这里没有下标的概念，所有查询通过关系来操作。
				current = current.next;
			}else{
				System.out.println("没有找到数据");
				current = null;
				break;
			}
		}
		return current;
	}
	
	//删除：主需要将删除链接点的前一个链接点的next地址指向删除链接点的下一个链接点位置。
	//链表删除不需要考虑链表中的其他数据，之需要改变删除连接之前链接点的地址而已。
	//操作的对象只有删除链接点的前后两个链接点。其他链接点不需要操作，因为他们不像数组
	//依靠位置来决定数据的，这里只是根据关系来操作，抽象说只是操作链接点指向，也就是改变关系。
	public void deleteLike(int key){
		//当前链接点
		Link current = first;
		//前一个链接点
		Link privous = first;
		
		boolean isfind = true;
		
		//判断是否是要删除的链接点
		while(current.iData != key){
			//如果还有下一个链接点，更换当前的两个链接点
			if(current.next != null){
				//两个链接点均想后移动一位，继续判断
				privous = current;
				current = current.next;
			}else{
				System.out.println("no find the Data");
				current = null;
				isfind = false;
				break;
			}
		}
		//判断是否找到要删除的数据
		if(isfind == true){
			//如果要删除的是首个链接点，则将first 指向当前链接点的下一个点，first.next
			if(current == first){
				first = first.next;
			}else{
				//如果不是删除首链接点，则将要删除的链接点的前一个链接点的next地址指向
				//删除点的下一个链接点即可。
				//注意：删除操作只是改变的链接点的指向，并没有实际删除了数据。该数据将被回收机制处理。
				privous.next = current.next;
			}
		}else{
			System.out.println("no find the Data of delete");
		}
		
		
	}
	
	public Link displayList(){
		System.out.println("List (fist - -> last )");
		Link top = first;
		while(top!= null){
			top.displayLink();
			top = top.next;
		};
		return top;
	}
	
	public boolean isEmpty(){
		return (first == null );
	}
}

//链接点对象
class Link{
	public int iData;
	public double dData;
	
	//关系子段，用于存储下一个链接点的位置
	public Link next;
	public Link(int id, double dd){
		this.iData = id;
		this.dData = dd;
	}
	public void displayLink(){
		System.out.println("{" + iData + "," + dData + "}");
	}
}