网站相册优化/摘抄一则新闻

其实跟C语言创建单链表，尾部插入结点操作的是一样的，本质上是一样的

双端链表与传统的链表非常相似，但是他有一个新增的特性：即对最后一个链结点的引用，就像对第一个链结点的引用一样。对最后一个链结点的引用允许像在表头一样，在表尾直接插入一个链结点。
 当然，仍然可以在普通的单链表表尾插入一个链结点，方法是遍历整个链表知道到达表尾，但是这种方法效率很低。像访问表头一样访问表尾的特性，使双端链表更适合于一些普通链表不方便操作的场合，
 队列的实现就是这样一个情况；注：双端链表不是双向链表

双端链表类叫做FirstLastList。正如前面讨论的，它有两个项，first和last，一个指向链表中的第一个链结点，另一个指向最后一个链结点。
 如果链表中只有一个链结点，first和last就都指向它，如果没有链结点，两者都为null值。

代码如下，详细注释：

/*** 定义一个结点类* @author Administrator**/
public class Link {public int data;	//数据域public Link next;	//指向下一个结点public Link(int data) {super();this.data = data;}//打印结点的数据域public void diaplayLink() {System.out.print("{"+ data + "} ");}
}

/*** 建立双端链表 * @author Administrator**/
public class FirstLastLink {private Link first;private Link last;public FirstLastLink() {first = null;last = null;}public boolean isEmpty() {return (first==null);}//头部插入,last永远指向的是第一个插入的结点,头部插入的特点就是会逆置public void inserstFirst(int data) {Link newNode = new Link(data);if(isEmpty()) {					//如果链表是空的即first==null，则代表我们将要插入第一个结点last = newNode;				//last永远指向的是第一个我们插入的结点}newNode.next = first;			//跟我们初始单链表的时候一样，在头部插入，先将新的结点的next域指向老的结点，以插入第二个结点为例：first = newNode; 				//1、first--->（指向）第一个结点}									//2、将新的结点newNode.next---> first(即新的结点next指向第一个结点)//first = newNode  first指向第二个结点即最新插入的结点 	//尾部插入,last永远指向最新插入的结点public void insertLast(int data) {Link newNode = new Link(data);if(isEmpty()) {					//如果链表是空的，则将last指向第一个数据结点newNode.next = null;		//newNode.next = null;这条语句其实不是必须的，只是为了方便大家理解first = newNode;			//将first指向第一个结点}else {last.next = newNode;		//last此时指向的是上次插入的结点，比如说现在我们插入的是第二个结点，那么此时，last指向的是第一个数据结点newNode.next = null;		//同上面一样newNode.next = null;这条语句其实不是必须的，只是为了方便大家理解}last = newNode;					//上述已经完成了将新的数据结点插入链表，最后则是将last指向最新的结点}public Link deleteFirst() {				//从头部删除结点返回结点Link temp = first;if(first.next==null)			//如果只有一个结点，则删除后链表为空，则返回null return null;first = first.next;				//若不是，则将first指向第二个结点return temp;}//删除最后一个结点,该操作比较繁琐，不太推荐使用，效率低下public Link deleteLast() {Link current = first;			//定义当前结点	Link temp = first;				//定义一个标志结点，后面会用到if(isEmpty()) {					//如果链表是空的，则返回nullreturn null;}else if(current.next==null) {	//否则如果链表的下一个是空的话，也就是说链表只有一个结点，此时我们要删除它first = null;				//则first指向null，意味着第一个数据结点被删除，此时链表为空return current;}else {while(current.next.next!=null) {	//循环，如果当前结点的next的next为空的话，意味着当前结点的下一个结点时最后一个结点，我们要删除它current = current.next;			//如果current.next.next==null，退出循环，说明我们找到了倒数第二个结点}									//将最后一个结点赋给temp，然后将current.next即倒数第二个结点赋null，称为最后一个结电，在最后将temp返回temp = current.next;current.next = null;return temp;}}//删除指定数据的结点public Link delete(int key) {Link current = first;			//获取当前结点Link previous = first;			//获取当前结点，方便删除结点while(current.data!=key) {		//只要当前数据不等于key，则一直遍历下去if(current.next == null) {	//如果current.next==null表示当前结点是最后一个结点或者链表为空，意味着找不到key，返回nullreturn null;}else {previous = current;		//否则将当前结点赋给previous表示上一个结点current = current.next  ;	//然后将当前结点的下一个结点赋给当前结点，即current = current.next}}if(current==first) {		//如果current==first，表示第一个结点的data与key是相等的，为了删除该结点，first指向first.next（即第二个结点）first = first.next;		//和delete操作相同}else {previous.next = current.next;	//否则将current即当前结点的上一个结点previous.next和下一个结点current.next相连}return current;		//返回删除的结点}public void displayList() {//System.out.print("List(first--->last): ");Link current = first;while(current!=null) {current.diaplayLink();current = current.next;}System.out.println();}}

/*** 测试双端链表* @author Administrator**/
public class TestFirstLastLink {public static void main(String[] args) {FirstLastLink theList = new FirstLastLink();//在头部插入theList.inserstFirst(22);theList.inserstFirst(44);theList.inserstFirst(66);//在尾部插入theList.insertLast(11);theList.insertLast(33);theList.insertLast(55);//演绎链表theList.displayList();//删除结点(头部删除)theList.deleteFirst();theList.delete(22);theList.deleteLast();theList.displayList();}
}

测试结果如下：

List(first--->last): {66} {44} {22} {11} {33} {55} 
List(first--->last): {44} {11} {33} 
 

链表的效率：
    在表头插入和删除速度很快。仅需要改变一两个引用值，所以话费O(1)的时间。
    平均起来，查找、删除和在指定链结点后面插入都需要搜索链表中的一般链结点。需要O(N)次比较。在数组中执行这些操作也需要O(N)次比较，但是链表仍然要快一些，因为当插入和删除链结点时，链表不需要移动任何东西。增加的效率是很显著的，特别是当复制时间远远大于比较时间的时候。
    当然，链表比数组优越的另外一个重要方面是链表需要多少内存就可以用多少内存，并且可以扩展到所有可用内存。数组的大小在它创建的时候就固定了；所以经常由于数组太大导致效率低下或者数组太小导致空间溢出。向量是一种可可扩展的数组，它可以通过可变长度解决这个问题，但是它经常只允许以固定大小的增量扩展（例如快要溢出的时候，就增加一倍数组容量）。
这个解决方案在内存使用效率上来说还是要比链表的低。