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等等的方法。篇中有错误的地方欢迎指出,有问题欢迎交流。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Android机动车

Java 基础(四)——集合源码解析 List

前面我们学习了Iterator、Collection,为集合的学习打下了基础,现在我们来学习集合的第一大体系 List。

754
来自专栏和蔼的张星的图像处理专栏

156. 合并区间先排序再处理

给出若干闭合区间,合并所有重叠的部分。 样例 给出的区间列表 => 合并后的区间列表:

743
来自专栏zaking's

用js来实现那些数据结构08(链表02-双向链表)

  其实无论在任何语言中,一种数据结构往往会有很多的延伸和变种以应对不同场景的需要。其实前面我们所学过的栈和队列也是可以用链表来实现的。有兴趣的小伙伴可以自己尝...

2716
来自专栏菜鸟前端工程师

JavaScript学习笔记023-对象方法0包装对象0静态属性

602
来自专栏程序生活

Leetcode-Easy 461.Hamming Distance

Leetcode-Easy是Leecode难度为"Easy"的解法,由python编码实现。 461.Hamming Distance 描述: ? 思路: 首...

2665
来自专栏鸿的学习笔记

Python和Scala的定义变量

每一门的编程语言背后都代表着某一种特别的哲学,由这一哲学进而设计出属于这门程序语言的语法,Python和Scala也不例外。我们从变量的定义去一窥Python和...

792
来自专栏Python中文社区

Python元编程:控制你想控制的一切

專 欄 ❈松直,Python中文社区专栏作者,计算机在读,Python拥趸,知乎专栏:从Python开始❈ 很多人不理解“元编程”是个什么东西,关于它也没有一...

1858
来自专栏顶级程序员

为什么Java中1000==1000为false而100==100为true?

原文:Why 1000 == 1000 Returns False, but 100 == 100 Returns True in Java? 作者:Bazl...

2607
来自专栏web前端教室

挖坑无止境,来看看这个《this的指向》

无事乱翻书,偶然发现这个东西: var length = 10; function fn() { console.log(this.length); }...

1846
来自专栏风中追风

高效编程之HashMap的entryset和keyset比较

最近看了一点spring的源码,甚是苦涩;对spring稍微有了点整体的认识,但对很多细节的地方还是懵逼啊。。。太多不懂了的,只能慢慢去读,先把简单的不懂的解决...

33810

扫码关注云+社区