欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构-链表

程序员文章站 2022-05-11 12:44:30
...

【节点】

 数据域(Object对象)

指针域(节点对象)

【链表】

由一个或多个节点组成的一种数据结构,具有散列的存储结构;

【链表的分类】

单向链表、双向链表、循环链表

【数组队列&链表】

数组队列可以实现定位,但每次增减元素都要新创建一个数组;

链表不能定位,查找数据的时候,必须从根节点开始遍历,但链表可以插入和删除任意位置的节点,可以充分利用计算机内存空间;

【节点类】

public class Node {
	public Object data;
	public Node next;
	//构造方法,设置数据域
	public Node(Object data){
		this.data = data;
	}

【单向链表的实现】

public class MyLinked {
	public Node root;
	public Node rear;
	int size = 0;
	//多次用到,定义一个方法
	public Node search(int index){
		Node tempnode = root;
		for(int i=0;i<index;i++){
			tempnode = tempnode.next;
		}
		return tempnode;
	}
	
	//添加节点 ~
	public void add(Object data){
		//创建一个节点
		Node node = new Node(data);
		//判断加入的为第一个节点
		if(root ==null && rear == null){
			root = node;
			rear = node;
		}
		//以后的节点
		else{
			rear.next = node;
			rear = node;//把新节点赋给根节点
		}
		size++;
	}
	
	//根据索引删除节点,索引从0起 ~
	public boolean remove(int index){
		//判断是否合法
		if(index <0 || index>size-1){
			return false;
		}
		else {
			//判断要删除的是否为根节点
			//  是 ,删除根节点
			if(index == 0){
				root= root.next;
			}
			//否,
			else{
				//把两个节点串起来
				Node tempnode = this.search(index-1);//取出索引节点前一个节点
				Node snode = tempnode.next;//保存索引位置节点
				tempnode.next =snode.next;//索引位置前一个节点指向索引位置后一个节点				
			}
			size--;
			return true;
		}
	}
	
	//根据数据删除节点 ~
	public boolean remove(Object data){
		Boolean flag = false ;
		for(int i=0;i<size-1;i++){
			if(this.get(i)==data){
				//把两个节点串起来
				Node tempnode = this.search(i-1);//取出目标节点前一个节点
				Node snode = tempnode.next;//保存索引位置节点
				tempnode.next =snode.next;//索引位置前一个节点指向索引位置后一个节点
				size--;
				flag = true;// 循环里面 要用flag
			}	
		}
		return flag;
	}
	
	//在索引前插入节点,参数:索引在前 ~
	public boolean insert(int index,Object data){
		Node node = new Node(data);
		//判断索引数值是否合法
		if(index <0 || index>size-1){
			return false;
		}
		else{
		//先判断要插入的是否为根节点
			//插在根节点前
			if(index == 0){
				node.next = root;
				root = node;
				size++;
				return true;
			}
			else{
				Node tempnode = this.search(index-1);//找到索引位置的前一个节点

				//把三个节点串起来
				Node snode = tempnode.next;//保存索引位置节点
				node.next = snode;// 新节点指向索引位置节点
				tempnode.next = node;//索引位置前节点指向新节点
				
				size++;
				return true;
			}
		}
		
	}
	
	//修改节点数据,根据索引  ~	
	public boolean set(int index,Object data){
		if(index <0 || index>size-1){
			return false;
		}
		else{
			Node tempnode = this.search(index);//找到索引位置的节点
			tempnode.data = data;//修改索引位置节点的数据域
			return true;
		}
	}
	
	//修改节点数据,根据数据 ~
	public boolean set(Object aim,Object data){
		Boolean flag = false;
		//循环 遍历节点
		for(int i=0;i<size;i++){
			if(this.get(i)==aim){
				Node tempnode = this.search(i);//获取目标节点					
				tempnode.data = data;//直接修改数据域
				flag = true;
			}			
		}
		return flag;
	}
	
	//获取指定索引数据 ~
	public Object get(int index){
		if(index <0 || index>size-1){
			return false;
		}
		else{
			Node tempnode = this.search(index);
			return tempnode.data;
		}
	}
	
	//获取节点总数 ~
	public int size(){
		return size;
	}
}

 

【Tips】

(1)参数中有索引的方法,一定要率先判断索引数是否在合法范围内;

(2)对节点进行插入、删除操作时,要考虑到根节点和其他节点的不同;

(3)多次用到的一段代码,可以把他写成一个函数,直接调用;

//多次用到,定义一个方法
	public Node search(int index){
		Node tempnode = root;
		for(int i=0;i<index;i++){
			tempnode = tempnode.next;
		}
		return tempnode;
	}

 (4)区分数据和节点,打印链表的时候需要返回数据,对节点进行操作寻找目标节点是需要返回节点,而不是具有节点数据的新的节点;

(5)返回值为boolean,是为了在调用函数的时候根据 返回值为true或false来进行对操作是否成功的提示。

相关标签: 学习总结