创建双向链表，并实现增、删、改、查

 

package 链表;
/*
 *    链表是一种常见的数据结构，不同于数组有固定的长度，它是动态进行存储分配的一种结构。
 * 例如一个班级有50人，但是另外一个班级只有40人，如果用数组存储它们需要定义一个长度
 * 为50的数组，而其他班级并没有这么多人，这将会浪费许多的存储空间。
 *    每个链表都有一个头指针，指向第一个节点。通常每个节点分为两个部分，用户存放的数据
 * 和指向下一个节点的地址。每个节点依次向下指向，最后一个指向一个NULL表示链表结束。
 *    在操作链表时，头指针一般不动（方便遍历所有链表数据），通常重新定义一个新的指针与
 * 头指针指向相同地址，来进行数据操作。
 * C语言创建链表主要代码：
 *    struct student
 *    {
 *    	int data;
 *    	struct student *next;
 *    }
 *    void main()
 *    {
 *    	struct student *head;
 *    	struct student *p1,*p2;
 *    	int n=0;
 *    	p1=p2=(struct student*)malloc(sizeof(struct student));
 *    	scanf("%d",&p1->data);
 *    	head=NULL;
 *    	while(p1->data!=0)
 *    	{
 *    	    n++;
 *    	    if(n==1) 
 *    	    {
 *    	       head=p1;
 *    	     }else{
 *    		     p2->next=p1;
 *    		   }
 *    	     p2 = p1;	
 *    	     p1=(struct student*)malloc(sizeof(struct student));
 *    	     scanf("%d",&p1->data);	
 *    	}
 *    p2->next=NULL;
 *    }
 *    从上述C语言创建链表可见流程较为繁琐，数据分布在内存任意位置，通过指针指向下一个地
 * 址来关联，所以在查找数据时链表没有数组直观且效率高，但是链表在进行增加、删除、插入时效
 * 率比数组要好，因为链表只需要改变指针指向就可以达到增加、删除、插入效果，而数组则需要重
 * 新给它们的位置排序效率低。
 *    下面代码使用Java语言编写的链表，不同于C语言，Java没有指针概念，而是通过节点的引
 * 用与下一个节点产生联系。创建了一个双向链表，可以向下遍历，同时可以向上遍历，且实现了链
 * 表的增、删、改、查操作。(上课时老师编写的代码并没有完全实现双向链表增、删、改、查等功
 * 能，我已经将代码完善。)
 */

public class MyLinkList<E> {
	
	private Node <E> head = null;//头节点
	private Node <E> last = null;//尾节点
	private int num = 0;//节点个数
	
	public MyLinkList(){}
	
	public void add(E e){//增加链表节点
		Node<E> node = new Node<E>(e);//创建一个新的节点
		if(last != null)//如果尾节点last不等于空，则向后添加新的节点。
		{
			last.next = node;
			node.front = last;
			last = node;//尾节点last向后移动
			last.next = null;//且尾节点last下一个等于空，表示链表结束
		}
		else {//如果尾节点last等于空，说明这是第一个节点，需要把新节点node定义为头、尾节点
			head = node;
			head.front = null;//头节点head上一个为空
			last = node;
		}
		num++;//节点个数加1
	}
	public void intsert(int index,E e)//在链表第index个位置插入节点
	{
		Node<E> node = new Node<E>(e);
		Node<E> n1 = getMode(index);//通过getMode方法返回第index个节点
		if(index == 0){//index等于0是头节点
			node.next = n1;
			node.front = null;
			head = node;
			n1.front = node;
		}else if(index == num-1){//index等于num-1是尾节点
			Node<E> n2 = n1.front;
			n2.next = node;
			node.front = n2;
			node.next = n1;
			n1.front = node;
			last = n1;
			last.next = null;
		}else{
			Node<E> n2 = n1.front;
			n2.next = node;
			node.front = n2;
			node.next = n1;
			n1.front = node;
		}
		num++;
	}
	public void delete(int index){//删除第index个节点
		if(index >= 0 && index <num){
			if(index==0){
				head=head.next;
				head.front = null;
			}else if(index==num-1){
				last = last.front;
				last.next =null;
			}else{
				Node<E> n1 = getMode(index);
				Node<E> n2 = n1.front;
				n2.next=n1.next;
				n2 = n1.next.front;
			}
			num--;
		}else{
			throw new IndexOutOfBoundsException("下标超出范围：index"+index+",size"+num);
		}
	}
	public void delete(E e){//删除链表中的某个数据的节点
		int index = First(e);//获得第一个节点的位置
		delete(index);
	}
	public void update(int index,E e){//更新第index个的数据
		Node<E> node = getMode(index);
		node.data = e;
	}
	public int First(E e)//查找第一个符合要求的位置
	{
		Node<E> node = head;
		int index=-1;
		while (node != null)
		{
			index++;
			if(node.data.equals(e)){
				break;
			}
			node=node.next;
		}
		return index;
	}
	public int Last(E e)//查找最后一个符合要求的位置
	{
		Node<E> node = last;
		int index=num;
		while (node != null)
		{
			index--;
			if(node.data.equals(e)){
				break;
			}
			node=node.front;
		}
		return index;
	}
	public E get(int index){//正向获取第index个节点的数据
		Node<E> node = getMode(index);
		return node.data;
	}
	public E getlast(int index){//反向获取第index个节点的数据
		Node<E> node = getlastMode(index);
		return node.data;
	}
	private Node<E> getMode(int index){//正向获取第index个节点的数据的具体方法
		int t = -1;
		if(index >= 0 && index <num){
			Node<E> n = head;
			while(n != null)
			{
				t++;
				if(t == index){
					break;
				}
				n=n.next;	
			}
			return n;
		}else {
			throw new IndexOutOfBoundsException("下标超出范围：index"+index+",size"+num);
		}
	}
	private Node<E> getlastMode(int index){//反向获取第index个节点的数据的具体方法
		int t = num;
		if(index >= 0 && index <num){
			Node<E> n = last;
			while(n != null)
			{
				t--;
				if(t == index){
					break;
				}
				n=n.front;	
			}
			return n;
		}else {
			throw new IndexOutOfBoundsException("下标超出范围：index"+index+",size"+num);
		}
	}
	public void HeadInquire()//从头开始遍历链表
	{
		Node<E> node = new Node<E>();
		node = head;
		while(node != null){
			System.out.println(node.data);
			node = node.next;
		}
	}
	public void LastInquire()//从尾开始遍历链表
	{
		Node<E> node = new Node<E>();
		node = last;
		while(node != null){
			System.out.println(node.data);
			node = node.front;
		}
	}
	public int size(){//获取节点个数
		return num;
	}
}
class Node<E>{
	
	E data;
	Node<E> next;// 对下一个节点的引用
	Node<E> front;// 对前一个节点的引用
	public Node(){
		
	}
	public Node(E e){
		this.data = e;
	}
}

package 链表;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated constructor stub
		MyLinkList<String> node = new MyLinkList<String>();
		for(Character i=65;i<70;i++){
			node.add(i.toString());//增加链表节点
		}
//		node.intsert(0, "HH");//插入几点
//		node.delete(4);//根据节点位置删除节点
//		node.delete("A");//根据内容删除符合要求的第一个节点
//		node.update(1, "E");//通过节点位置更新内容
//		System.out.println(node.First("E"));//查找第一个符合要求的位置
//		System.out.println(node.Last("E"));//查找最后一个符合要求的位置
//		for(int i=0;i<node.size();i++){//通过链表节点个数正向遍历链表
//			String s=node.get(i);
//			System.out.println(s);
//		}
//		for(int i=node.size()-1;i>=0;i--){//通过链表节点个数反向遍历链表
//			String s=node.getlast(i);
//			System.out.println(s);
//		}
		node.HeadInquire();//通过链表是否为空正向遍历链表
//		node.LastInquire();//通过链表是否为空正向遍历链表
	}
}