Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

数据结构之链表解析

Kevin.ZhangCG 2019-02-20 10:42:00 阅读数:139 评论数:0 点赞数:0 收藏数:0

我们知道,数组作为数据存储结构有一定的缺陷。在无序数组中,搜索时低效的;而在有序数组中,插入效率又很低;不管在哪一种数组中删除效率都很低。况且一个数组创建后,它的大小是无法改变的。而链表可能是继数组之后第二种使用得最广泛的通用数据结构了。这里主要来讨论并写一个单链表和双向链表。

顾名思义,单链表只能从表头到表尾的顺序,每个节点中保存了指向下一个节点的指针;双向链表则可以反向遍历,因为节点中既保存了向后节点的指针,又保存了向前节点的指针。由于链表结构相对简单,这里不再赘述,直接通过程序来查看它们常见的操作:

单链表

 public classLink {public intdata;publicLink next;public Link(intdata) {this.data =data; next= null; }public voiddisplayLink() { System.out.print("[ " + data + " ]"); } }

 

 public classLinkedList {//头节点 privateLink first;//链表中节点数量 private intnElem;//添加头结点 public void insertFirst(intvalue) { Link newLink= newLink(value);//newLink --> old first newLink.next =first;//first --> newLink first =newLink; nElem++; }//删除头结点 publicLink deleteFirst() {if(isEmpty()) { System.out.println("The Link is empty!");return null; } Link temp=first; first=first.next; nElem--;returntemp; }//下面是有序链表的插入 / 这样简单排序就可以用链表来实现,复杂度为O(n) / 定义一个方法,传入一个数组 / 在方法内,遍历数组并调用insert方法就可以将数组中的数据排好序/*/ public void insert(intvalue) { Link newLink= newLink(value); Link current=first; Link previous= null;while (current != null && value >current.data) { previous=current; current=current.next; }if (previous == null) { first=newLink; }else{ previous.next=newLink; } newLink.next=current.next; nElem++; }//查找特定节点 public Link find(intvalue) { Link current=first;while (current.data !=value) {if (current.next == null) {return null; } current=current.next; }returncurrent; }//删除特定节点 public Link delete(intvalue) { Link current=first; Link previous=first;while (current.data !=value) {if (current.next == null) {return null; } previous=current; current=current.next; }if (current ==first) { first.next=first; }else{ previous.next=current.next; } nElem--;returncurrent; }public voiddisplay() {if(isEmpty()) { System.out.println("The link is empty!");return; } Link current=first;while (current != null) { current.displayLink(); current=current.next; } System.out.println(" "); }public booleanisEmpty() {return (first == null); }public intsize() {returnnElem; } }

 

双向链表

public classNode {public longdata;publicNode previous;publicNode next;public Node(longvalue) {this.data =value; previous= null; next= null; }public voiddisplay() { System.out.print("[" + data + "]"); } }

public classDoublyLinkedList {//头结点 privateNode first;//尾节点 privateNode last;private intsize;publicDoublyLinkedList() { first= null; last= null; size= 0; }//插入头结点 public void insertFirst(longvalue) { Node newNode= newNode(value);if(isEmpty()) { first=newNode; }else{//newLink <-- oldFirst.previous first.previous =newNode;//newLink --> first newNode.next =first; }//first --> newLink first =newNode; size++; }//插入尾节点 public void insertLast(longvalue) { Node newNode= newNode(value);if(isEmpty()) { last=newNode; }else{//newlink <-- oldLast.newxt last.next =newNode;//newLink.previous --> last newNode.previous =last; } last=newNode; size++; }//删除头结点 publicNode deleteFirst() { Node temp=first;if(isEmpty()) { System.out.println("The link is Empty!");return null; }//只有一个节点 if (first.next == null) { last= null; }else{ first.next.previous= null; } first=first.next; size--;returntemp; }//删除尾节点 publicNode deleteLast() { Node temp=last;if(isEmpty()) { System.out.println("The link is empty!");return null; }//只有一个节点 if (last.previous == null) { first= null; }else{ last.previous.next= null; } last=last.previous; size--;returntemp; }public boolean insertAfter(long key, longvalue) { Node current=first;while (current.data !=key) { current=current.next;if (current == null) {return false; } }if (current ==last) { insertLast(value); }else{ Node newNode= newNode(value); newNode.next=current.next; current.next.previous=newNode; newNode.previous=current; current.next=newNode; size++; }return true; }public Node deleteNode(longvalue) { Node current=first;while (current.data !=value) { current=current.next;if (current == null) {return null; } }if (current ==first) { deleteFirst(); }else if (current ==last) { deleteLast(); }else{ current.previous.next=current.next; current.next.previous=current.previous; size--; }returncurrent; }public intsize() {returnsize; }public booleanisEmpty() {return (first == null); }//从头到尾遍历链表 public voiddisplayForward() { Node current=first;while (current != null) { current.display(); current=current.next; } System.out.println(); }//从未到头遍历链表 public voiddisplayBackward() { Node current=last;while (current != null) { current.display(); current=current.previous; } System.out.println(); } }

在表头插入和删除速度很快,仅需改变一两个引用值,所以花费 O(1) 的时间。平均起来,查找、删除和在指定节点后面插入都需要搜索链表中的一半节点,需要O(N)次比较。在数组中执行这些操作也需要 O(N) 次比较,但是链表仍然要比数组快一些,因为当插入和删除节点时,链表不需要移动任何东西,增加的效率是很显著的,特别是当复制时间远远大于比较时间的时候。

当然,链表比数组优越的另一个重要方面是链表需要多少内存就可以用多少内存并且可以扩展到所有可用内存。数组的大小在它创建的时候就固定了,所以经常由于数组太大导致效率低下,或者数组太小导致空间溢出。可变数组可以解决这个问题,但是它经常只允许以固定大小的增量扩展,这个解决方案在内存使用率上来说还是比链表要低。

 

版权声明
本文为[Kevin.ZhangCG]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/Kevin-ZhangCG/p/10309581.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;