用java实现简单的链表

? ? ? ? ? ?链表不同于以前我们学过的队列或数组，它是非线性的，即不是在内存中连续存储的。链表可以理解成由很多结点组成，很多人会把链表比喻为自行车的链条，这一点我觉得有点不怎么适合因为链表也可以是无序的比如张三有李四的电话号码王五也有李四电话号码，那么张三要找王五就只需通过李四就可以了，他们可以是所在位置的不同，当然我这里只是做了一个比喻有可能不太妥当，我们一般将链表的一个结点分成两个部分：Data filed和Pointer field（这些是作者沿用C里的叫法），数据域用来存储数据，域用后面的指针来存放下一个结点的地址。?

下面我用一个类来举例我在这里只实现的删除和增加的是功能，为了让代码的简洁我用了一个内部类

?

public class LinkList {
	
	Node head;
	Node end;
	int count;
	
	public void add(String s){
		Node n=new Node(s);
		if(head==null){
			head=n;
		}else{
			end.next=n;
			n.last=end;
		}
		end=n;
		count++;
	}

	public void delete(int index){
		Node n=getNode(index);
		Node n2=n.last;
		Node n3=n.next;
		if(n2==null){
			n3.last=null;
			head=n3;
		}else if(n3==null){
			n2.next=null;
			end=n2;
		}else{
			n2.next=n3;
			n3.last=n2;
		}
		count--;
	}
	
	// 获得指定位置的元素值
	public String get(int index){
		Node n=getNode(index);
		String s=n.element;
		return s;
	}
	
	private Node getNode(int index){
		if(index<0||index>=size()){
			throw new RuntimeException("越界啦。。。");
		}
		int num=0;
		Node n=head;
		while(num<index){
			n=n.next;
			num++;
		}
		return n;
	}
	
	public int size(){
		return count;
	}
	//内部类
	class Node{
		String element;
		Node last;
		Node next;
		public Node(String element){
			this.element=element;
		}
	}
}

?add方法：

放入一个节点，如果链表中没有节点就作为头节点，如果有链表中有节点，就将该节点作为尾节点放入。

delete方法：

这里就需要做三次判断，需要判断链表中只有一个节点和两个节点的时候，如果这里不判断当删除的时候，他无法根据前后两个节点来判断你要删除的是那个节点，第三种情况就简单了。

?

下面我在简单说话所链表和数组的区别（所说的区别也就是用在的场景不同罢了）：

从逻辑结构来看
1. 数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费；数组可以根据下标直接存取。
2. 链表动态地进行存储分配，可以适应数据动态地增减的情况，且可以方便地插入、删除数据项。（数组中插入、删除数据项时，需要移动其它数据项，非常繁琐）链表必须根据next指针找到下一个元素
从内存存储来看。
（但链表也有区分? ? 按链表的组织形式分有ArrayList和LinkList两种。ArrayList内部其实是用数组的形式实现链表，比较适合链表大小确定或较少对链表进行增删操作的情况，同时对每个链表节点的访问时间都是constant；而LinkList内部以一个List实现链表，比较适合需要频繁对链表进行操作的情况，对链表节点的访问时间与链表长度有关O(N)这里需要具体问题集具体分析了。）

1. (静态)数组从栈中分配空间, 对于程序员方便快速,但是自由度小
2. 链表从堆中分配空间, 自由度大但是申请管理比较麻烦 

从上面的比较可以看出，如果需要快速访问数据，很少或不插入和删除元素，就应该用数组；相反， 如果需要经常插入和删除元素就需要用链表数据结构了。

?