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 条评论
登录 后参与评论

相关文章

来自专栏Java Edge

LinkedList源码分析(基于Java8)内部结构构造方法添加2检索3删除4迭代器5 例子6总结

3074
来自专栏小灰灰

Java容器篇小结之Map自问自答

采用问答的方式对常见的问题进行整理小结 I. Map篇 0. 什么是Map 看到这个有点懵逼,一时还真不知道怎么解释,能让完全没有接触过的人都能听懂 想到生活...

18410
来自专栏小勇DW3

LinkedHashMap 源码分析

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

1083
来自专栏swag code

练习-Map集合的操作

Teacher对象的值: “Tom”,”Java”, “John”,”Oracle”, “Susan”,”Oracle”, “Jerry”,”JDBC”...

883
来自专栏chenssy

【死磕Java并发】-----J.U.C之阻塞队列:PriorityBlockingQueue

我们知道线程Thread可以调用setPriority(int newPriority)来设置优先级的,线程优先级高的线程先执行,优先级低的后执行。而前面介绍的...

3234
来自专栏开发与安全

散列表(二):冲突处理的方法之链地址法的实现(哈希查找)

首先需要澄清的一点是,这里讲的是hash table/hash map ,即数据项所存储的表要用数组来实现。 一、链地址法 这种基本思想:将所有哈希地址为i 的...

1900
来自专栏开发之途

Java集合框架源码解析之LinkedList

1093
来自专栏butterfly100

ConcurrentHashMap源码阅读

1. 前言 HashMap是非线程安全的,在多线程访问时没有同步机制,并发场景下put操作可能导致同一数组下的链表形成闭环,get时候出现死循环,导致CPU利用...

2667
来自专栏cmazxiaoma的架构师之路

通过分析LinkedHashMap了解LRU

我们都知道LRU是最近最少使用,根据数据的历史访问记录来进行淘汰数据的。其核心思想是如果数据最近被访问过,那么将来访问的几率也更高。在这里提一下,Redis缓存...

643
来自专栏F_Alex

数据结构与算法(二)-线性表之单链表顺序存储和链式存储

前言:前面已经介绍过数据结构和算法的基本概念,下面就开始总结一下数据结构中逻辑结构下的分支——线性结构线性表

862

扫码关注云+社区