数据结构-链表

本文主要来简单介绍一下数据结构之链表

1. 准备数据

本文所使用数据结构如代码所示

class Data{
	String name;
    String key;
    int age;
}       //存储数据结构

class LinkNode{
	Data data = new Data();
    Data nextData;
}

2. 追加节点

在链表的末尾追加指定的节点

LinkNode addEnd(LinkNode head, Data nodeData){
	LinkNode node,htemp;
	if((node = new LinkNode())==null){
		System.out.println("申请内存失败");
		return null;
	}
	else{
		node.nodeData = nodeData; //要插入的节点
		node.nextNode = null;
		if(head == null){
			return node; //判断待插入的链表是否为空
		}
		else{
			htemp = head;
			while(htemp.nextNode!=null){
				htemp = htemp.nextNode;
			}
			htemp.nextNode = nodeData;
			return head
		}
	}
}

3. 查找节点

查找链表中的某个节点key值是与给定的key值相等

LinkNode findNode(LinkNode head, String key){
	LinkNode node;  //用户返回查找到的节点
	while(LinkNode!=null){
		if(LinkNode.nodeData.key.compareTo(key)==0){   //String.compareTo()函数比较字符串的内容，相等为0，>0和<0分别代表前者大于和小于后者，数值即为两者相差的ASCII值，==比较字符串在内存中的地址是否相等
			return LinkNode;
		}
		LinkNode = LinkNode.nextNode;
	}
	return null;
}

4. 插入节点

4-1. 在链表头部插入节点

LinkNode insertHead(LinkNode head, Data nodeData){
	LinkNode node;
	if((node = new LinkNode()) == null){
		System.out.println("申请内存失败");
		return null;
	}
	else{
		node.nodeData = nodeData;
		node.nextNode = head;
		return node;
	}
}

4-2. 在链表中间插入节点

LinkNode insertMiddle(LinkNode head, Data nodeData, String findKey){
	LinkNode node;
	if((node = new LinkNode()) == null){
		System.out.println("申请内存失败");
		return null;
	}
	htemp = findNode(head, findKey);//查找需要插入的节点位置
	if(htemp!=null){
		node.nodeData = nodeData;
		node.nextNode = htemp.nextNode;
		htemp.nextNode = node;
		return head;
	}
	else{
		System.out.println('未找到正确的插入节点');
	}
}

5. 删除节点

LinkNode deleteNode(LinkNode head, String deleteKey){
	LinkNode node,temp;
	node = head;
	temp = head;
	if(head.nodeData.key.compareTo(deleteKey)==0){
		return head.nextNode;
	}
	else{
		while(temp!=null){
			if(temp.nodeData.key.compareTo(deleteKey)==0){
				node.nextNode = temp.nextNode;
				temp = null;
				return head;
			}
			else{
				node = temp;
				temp = temp.nextNode;
			}
		}
	}
	return null;
}