首页 > 代码库 > salesforce零基础学习（七十八）线性表链形结构简单实现
salesforce零基础学习（七十八）线性表链形结构简单实现
前两篇内容为栈和队列的顺序结构的实现，栈和队列都是特殊的线性表，线性表除了有顺序结构以外，还有线性结构。
一.线性表的链形结构--链表
使用顺序存储结构好处为实现方式使用数组方式，顺序是固定的。所以查询某个位置的元素特别容易，时间复杂度为O(1),但是当增加或者删除时，会需要将操作元素后面的元素整体向左或者向右平移。时间复杂度为O(n)。所以当线性表查询操作多于增删操作，优先使用顺序存储结构的线性表；当线性表增删操作多于查询操作，则优先使用链式存储结构的线性表。
线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。这就意味着，这些数据元素可以存在内存未被占用的任意位置。因为链表可以不连续的存储，所以每个元素需要记录一下他的后继的地址，从而实现每个不连续的元素之间实现关联。我们把元素内容信息和节点信息封装在一起，叫做结点。即每个结点拥有当前元素的信息以及此元素的后继结点的信息。
结点的代码描述可以为下方模型：这样可以通过某个结点获取其元素内容以及前一个和后一个结点。
1 private class Node { 2 Object item; // 当前节点所包含的值 3 Node next; //下一个节点 4 Node prev; //上一个节点 5 Node(Node prev, Object element, Node next) { 6 this.item = element; 7 this.next = next; 8 this.prev = prev; 9 } 10 }
二.链表功能的实现
链表作为线性表应该包含一些基础的功能，包括添加，修改，删除等。下方代码实现了以下的功能：
Integer size():返回链表的长度；
addFirst(Object obj):在链表第一个位置添加元素；
add(Object obj)：在链表尾部添加元素；
add(Object obj,Integer index):在指定位置添加元素，index从0开始；
Object removeFirst():移除列表中的第一个元素，并且返回它的值；
Object removeLast():移除列表中的最后一个元素，并且返回它的值；
Object remove(Integer index):移除指定位置的元素，index从0开始，并且返回它的值；
Boolean removeAll():移除所有的元素，成功返回true；
set(Integer index,Object obj):设置指定位置的value值；
Object[] toArray():将链表转换成数组，并返回数组；
toString()：重写toString()方法，返回的数据结构为(obj1,obj2,...objn)
上述方法中，如果出现数组越界或者其他情况下，返回自定义的异常。代码如下：
1 public without sharing class LinkedList { 2 3 private Integer size = 0; 4 5 private Node first; 6 7 private Node last; 8 9 public Integer size() { 10 return size; 11 } 12 13 //在第一个位置添加元素 14 public void addFirst(Object obj) { 15 linkNode(obj,0); 16 } 17 18 //在最后一个位置添加元素 19 public void add(Object obj) { 20 linkNode(obj,size); 21 } 22 23 //在指定位置前添加元素 24 public void add(Object obj,Integer index) { 25 linkNode(obj,index); 26 } 27 28 public Object removeFirst() { 29 return unLinkNode(0); 30 } 31 32 public Object removeLast() { 33 return unLinkNode(size - 1); 34 } 35 36 public Object remove(Integer index) { 37 return unLinkNode(index); 38 } 39 40 public Boolean removeAll() { 41 return (Boolean)unLinkNode(null); 42 } 43 44 public void set(Integer index,Object obj) { 45 checkPositionIndex(index,‘edit‘); 46 Node operateNode = node(index,‘edit‘); 47 operateNode.item = obj; 48 } 49 50 public Object[] toArray() { 51 Object[] results = new Object[size]; 52 Integer i = 0; 53 for(Node n = first;n != null;n = n.next) { 54 results[i++] = n.item; 55 } 56 return results; 57 } 58 59 public Object get(Integer index) { 60 checkPositionIndex(index,‘get‘); 61 Node result = node(index,‘get‘); 62 return result.item; 63 } 64 65 override public String toString() { 66 Object[] results = toArray(); 67 return String.valueOf(results); 68 } 69 70 private Object unLinkNode(Integer index) { 71 checkPositionIndex(index,‘delete‘); 72 Node leftNode; 73 Node rightNode; 74 Node operateNode; 75 Object result; 76 if(index != null) { 77 if(index == 0) {//remove first 78 operateNode = first; 79 result = operateNode.item; 80 rightNode = operateNode.next; 81 first = rightNode; 82 //如果只有一个结点，则将last置空 83 if(rightNode == null) { 84 last = null; 85 } else { 86 rightNode.prev = null; 87 } 88 size--; 89 } else if(index == size - 1) {//remove last 90 operateNode = last; 91 result = operateNode.item; 92 leftNode = operateNode.prev; 93 last = leftNode; 94 if(leftNode == null) { 95 first = null; 96 } else { 97 leftNode.next = null; 98 } 99 size--; 100 } else {//remove index node 101 operateNode = node(index,‘delete‘); 102 result = operateNode.item; 103 leftNode = operateNode.prev; 104 rightNode = operateNode.next; 105 if(leftNode != null) { 106 leftNode.next = rightNode; 107 } 108 if(rightNode != null) { 109 rightNode.prev = leftNode; 110 } else { 111 112 } 113 114 size--; 115 } 116 } else {//remove all 117 first = null; 118 last = null; 119 size = 0; 120 result = true; 121 } 122 return result; 123 } 124 125 private void linkNode(Object e,Integer index) { 126 checkPositionIndex(index,‘add‘); 127 Node newNode; 128 Node leftNode; 129 Node rightNode; 130 if(index == 0) {//add first 131 rightNode = first; 132 newNode = new Node(null,e,rightNode); 133 first = newNode; 134 if(rightNode == null) { 135 last = newNode; 136 } else { 137 rightNode.prev = newNode; 138 } 139 } else if(index == size) {//add last 140 leftNode = last; 141 newNode = new Node(leftNode,e,null); 142 last = newNode; 143 if(leftNode == null) { 144 first = newNode; 145 } else { 146 leftNode.next = newNode; 147 } 148 } else {//add node to specify index 149 //get the index node 150 rightNode = node(index,‘add‘); 151 leftNode = rightNode.prev; 152 newNode = new Node(leftNode,e,rightNode); 153 rightNode.prev = newNode; 154 if(leftNode == null) { 155 first = newNode; 156 } else { 157 leftNode.next = newNode; 158 } 159 } 160 size++; 161 } 162 163 //获取指定位置的结点元素，此部分可以进行优化。比如二分法或者其他处理从而减小循环的数量 164 private Node node(Integer index,String operateType) { 165 checkPositionIndex(index,operateType); 166 Node x = first; 167 for(Integer i = 1;i < size;i++) { 168 x = x.next; 169 if(index == i) { 170 break; 171 } 172 } 173 return x; 174 } 175 176 //判断当前的index是否符合规范，比较其和size的关系以及是否大于0等校验 177 private void checkPositionIndex(Integer index,String operateType) { 178 179 if(index < 0) { 180 throw new LinkedListException(‘index必须大于等于0‘); 181 } 182 183 if(‘delete‘.equalsIgnorecase(operateType)) { 184 if(size <= 0) { 185 throw new LinkedListException(‘链表长度必须大于0才可以删除‘); 186 } 187 } 188 189 if(!‘add‘.equalsIgnorecase(operateType)) { 190 if(index >= size) { 191 throw new LinkedListException(‘index 越界！‘); 192 } 193 } 194 195 } 196 197 private class Node { 198 Object item; // 当前节点所包含的值 199 Node next; //下一个节点 200 Node prev; //上一个节点 201 202 Node(Node prev, Object element, Node next) { 203 this.item = element; 204 this.next = next; 205 this.prev = prev; 206 } 207 } 208 209 public class LinkedListException extends Exception { 210 211 } 212 }
三.测试结果
使用链表进行添加删除操作，并返回链表的值操作：
LinkedList ll = new LinkedList(); ll.add(‘aaa‘); System.debug(LoggingLevel.INFO, ‘*** 1: ‘ + ll); ll.addFirst(‘bbb‘); System.debug(LoggingLevel.INFO, ‘*** 2: ‘ + ll); ll.add(‘ccc‘,1); System.debug(LoggingLevel.INFO, ‘*** 3: ‘ + ll); ll.add(‘ddd‘); System.debug(LoggingLevel.INFO, ‘*** 4: ‘ + ll); System.debug(LoggingLevel.INFO, ‘*** ll.get(3): ‘ + ll.get(3)); ll.removeFirst(); System.debug(LoggingLevel.INFO, ‘*** 5: ‘ + ll); ll.remove(2); System.debug(LoggingLevel.INFO, ‘*** 6: ‘ + ll); ll.set(1, ‘set new obj‘); System.debug(LoggingLevel.INFO, ‘*** 7: ‘ + ll); System.debug(LoggingLevel.INFO, ‘*** ll.get(0): ‘ + ll.get(0)); Object[] objs = ll.toArray(); for(Object obj : objs) { System.debug(LoggingLevel.INFO, ‘*** obj: ‘ + obj); }
结果显示：
总结：此篇简单的实现了链表的数据结构以及最基本的方法，里面没有对空指针进行太多的处理，应该有很多隐藏的bug，感兴趣的可以去完善，比如完善一下构造函数传链表或者数组情况，getFirst,getLast等等的方法。篇中有错误的地方欢迎指出，有问题欢迎交流。
salesforce零基础学习（七十八）线性表链形结构简单实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。