首页 > 代码库 > 线性表的链式存储和实现
线性表的链式存储和实现
上篇讲了顺序表，这篇接着讲讲链式表的实现。
List.java
1 package com.yeyan.linklist; 2 3 /** 4 * 线性表接口 5 * @author yeyan 6 * @date 2014-12-07 7 * * API: 8 * isEmpty(): 判断该线性表是否为空 9 * length(): 表长10 * get(int index): 获得第index的元素11 * add(int index, T element): 在index位置之后添加一个元素12 * remove(index): 删除索引为index的元素 13 * clear() : 清除线性表14 *15 */16 17 public interface List<T> {18 public boolean isEmpty();19 public int length();20 public T get(int index) throws Exception;21 public boolean add(int index, T element) throws Exception;22 public T remove(int index) throws Exception;23 public void clear();24 }
Node.java
1 package com.yeyan.linklist; 2 /** 3 * 链表节点 4 * @author yeyan 5 * @date 2012-12-07 6 * @param <T> 7 */ 8 public class Node<T> { 9 //数据域10 public T data;11 //指针域，指向下一个节点12 public Node<T> next;13 14 // 首节点构造函数15 public Node(Node<T> next){16 this.next = next;17 }18 19 //其它节点构造函数20 public Node(T data, Node<T> next){21 this.data =http://www.mamicode.com/ data;22 this.next = next;23 }24 25 /**26 * 获取下一个节点27 */28 public Node<T> getNext(){29 return this.next;30 }31 /**32 * 设置下一个节点33 */34 public void setNext(Node<T> next){35 this.next = next;36 }37 /**38 * 获取当前节点数据39 */40 public T getData(){41 return this.data;42 }43 /**44 * 设置当前节点数据45 * @param data46 */47 public void setData(T data){48 this.data =http://www.mamicode.com/ data;49 }50 }
LinkList.java
1 package com.yeyan.linklist; 2 /** 3 * 链表的实现 4 * @author yeyan 5 * @date 2012-12-07 6 * @param <T> 7 */ 8 public class LinkList<T> implements List<T> { 9 // 头指针10 private Node<T> head;11 // 当前节点指针12 private Node<T> current;13 // 表长14 private int size;15 //初始化一个空表16 public LinkList(){17 this.head = this.current = new Node<T>(null);18 this.size = 0;19 }20 21 public void index(int index) throws Exception{22 if(index < -1 || index > size -1){23 throw new Exception("parameter error!");24 }25 if(index == -1)26 return;27 current = head.next;28 int i = 0;29 while(i < index){30 current = current.next;31 i ++;32 }33 }34 35 @Override36 public boolean isEmpty() {37 return size == 0;38 }39 40 @Override41 public int length() {42 return this.size;43 }44 45 @Override46 public Node<T> get(int index) throws Exception {47 int i = 0;48 current = head.next;49 while(i < index && current != null){50 current = current.next;51 i ++;52 }53 return current.next;54 }55 56 @Override57 public boolean add(int index, T data) throws Exception {58 if(index < -1 || index > size){59 throw new Exception("parameter error!");60 }61 index(index -1);62 current.setNext(new Node<T>(data, current.next));63 size ++;64 return true;65 }66 67 @Override68 public Node<T> remove(int index) throws Exception {69 Node<T> node = get(index);70 if(index < -1 || index > size){71 throw new Exception("parameter error!");72 }73 index(index -1);74 current.setNext(current.next.next);75 size --;76 return node;77 }78 79 @Override80 public void clear() {}81 }
链表的最大特点是：
插入、删除运算方便。
缺点：
（1）要占用额外的存储空间存储元素之间的关系，存储密度降低。存储密度是指一个节点中数据元素所占的存储单元和整个节点所占的存储单元之比。
（2）链表不是一种随机存储结构，不能随机存取元素。
与顺序表的比较
顺序存储是一种随机存取的结构，而链表则是一种顺序存取结构，因此它们对各种操作有完全不同的算法和时间复杂度。例如，要查找线性表中的第i个元素，对于顺序表可以直接计算出a(i)的的地址，不用去查找，其时间复杂度为0(1).而链表必须从链表头开始，依次向后查找，平均需要0(n)的时间。所以，如果经常做的运算是按序号访问数据元素，显然顺表优于链表。
反之，在顺序表中做插入，删除时平均移动表中一半的元素，当数据元素的信息量较大而且表比较长时，这一点是不应忽视的；在链表中作插入、删除，虽然要找插入位置，但操作是比较操作，从这个角度考虑显然后者优于前者。
线性表的链式存储和实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。