心得技巧
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧

从零开始学算法--自定义单链表

发布时间：2022-07-03 发布网站：脚本宝典
脚本宝典收集整理的这篇文章主要介绍了从零开始学算法--自定义单链表，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

链表分为单向链表，双向链表，单向循环列表，双向循环链表

所谓单向链表是指 链表中的每个节点包含数据域和一个指针域， 指针域指向下一个节点， 如下图所示

从零开始学算法--自定义单链表

 

 

 知道了单链表的数据结构， 那么我们就先定义节点内部类Node，它包含了数据域ITem和指针域nextNode

 1 public class SingleLinkedList<E>{
 2 
 3     /**
 4      * 节点
 5      *
 6      * @param <E>
 7      */
 8     class Node<E>{
 9         /**
10          * 元素
11          */
12         PRivate E item;
13         
14         /**
15          * 下个节点
16          */
17         private Node<E> nextNode;
18         
19         public Node(E item, Node<E> next){
20             this.item = item;
21             this.nextNode = next;
22         }
23         
24         @override
25         public String toString() {
26             return item.toString();
27         }
28     }
29 }

然后我们定义单链表的三个属性： 首节点，尾节点和size

 1 /**
 2      * 首节点
 3      */
 4     private Node<E> FirstNode;
 5     
 6     /**
 7      * 尾节点
 8      */
 9     private Node<E> lastNode;
10     
11     /**
12      * 链表长度
13      */
14     private int size;

定义add方法

向链表头部添加新节点， 我们需要 1，新节点的Next指针指向原本的firstNode

                                                         2, 新节点成为firstNode

向链表尾部添加新节点， 我们需要 1，lastNode的前一节节点的Next指针指向新节点

                                                         2, 新节点成为lastNode

 1 /**
 2      * 向链表尾部添加元素
 3      * @param e
 4      */
 5     public void add(E e) {
 6         if (size == 0) {
 7             linkFirst(e);
 8         }else {
 9             linkLast(e);
10         }
11     }
12 
13 /**
14      * 向链表首部插入元素
15      * @param e
16      */
17     private void linkFirst(E e) {
18         //插入之前的firstNode
19         Node<E> node = firstNode;
20         //因为在头部插入，所以新节点的NextNode指向原本的firstNode
21         Node<E> newNode = new Node(e, node);
22         //插入后首节点为newNode
23         firstNode = newNode;
24         //如果是空链表， 那么尾节点也等于首节点
25         if (size == 0) {
26             lastNode = newNode;
27         }
28         size++;
29     }
30     
31     /**
32      * 向链表尾部插入元素
33      * @param e
34      */
35     private void linkLast(E e) {
36         Node<E> node = lastNode;
37         Node<E> newNode = new Node(e, null);
38         lastNode = newNode;
39         //若插入之前为空链表
40         if (node == null) {
41             firstNode = newNode;
42         } else {
43             node.nextNode = lastNode;
44         }
45         
46         size++;
47     }

定义get方法

链表结构不支持随机查找， 所以查询时必须遍历链表来寻找对应的节点。 同时因为是单向链表，所以只能从firstNode开始遍历，根据Node.nextNode来查找下一个，代码如下：

 1 /**
 2      * 获取index位置上的节点元素
 3      * @param index
 4      * @return
 5      */
 6     public E get(int index) {
 7         Node<E> node = getNode(index);
 8         return node.item;
 9     }
10     
11     
12     private Node<E> getNode(int index) {
13         if (index<0 || index>size-1) {
14             throw new IndexOutOfBoundsException();
15         }
16         Node<E> node = firstNode;
17         for (int i = 0; i < index; i++) {
18             node = node.nextNode;
19         }
20         return node;
21     }

然后删除， 目前只写了删除首个节点的方法， 原理是  firstNode = firstNode.nextNode

删除指定Index节点的话，我们需要先找到index节点的前一个节点，改变它的指针，指向原本Index位置节点的后一个节点。

 1 /**
 2      * 删除第一个节点，并返回该节点的元素
 3      * @return
 4      */
 5     public E remove() {
 6         return unLinkFirst();
 7     }
 8     
 9     /**
10      * 删除第一个节点
11      * @return
12      */
13     private E unLinkFirst() {
14         Node<E> tempNode = firstNode;
15         if (size >0) {
16             Node<E> nextNode = firstNode.nextNode;
17             firstNode = nextNode;
18             size--;
19         }
20         return tempNode.item;
21     }

为了能用于上文从零开始学算法---线性表链式存储实现麻将排序 - 倒霉的菜鸟 - 博客园 (cnblogs.COM)测试， 再加一个addAll方法

public void addAll(SingleLinkedList<E> list) {
		for (int i = 0; i < list.size(); i++) {
			E node = list.get(i);
			if (size == 0) {
				linkFirst(node);
			}else {
				linkLast(node);
			}
		}
	}

　　以及在指定位置添加元素的add(index, e )方法 

 1 /**
 2      * 向链表指定位置添加元素
 3      * @param index
 4      * @param e
 5      */
 6     public void add(int index, E e) {
 7         if(index < 0 ) {
 8             throw new IndexOutOfBoundsException();
 9         }
10         if(index == 0) {
11             linkFirst(e);
12         }else if (index > size-1) {
13             linkLast(e);
14         }else {
15             //找到指定位置的前一个节点
16             Node<E> preNode = getNode(index-1);
17             //找到指定位置的节点
18             Node<E> node = preNode.nextNode;
19             //新加入的节点的Next指向当前index位置的节点
20             Node<E> newNode = new Node(e, node);
21             //让前一个节点的Next指向要插入的节点
22             preNode.nextNode = newNode;
23             size++;
24         }
25     }

 

测试代码如下 ：

 1 public static void main(String[] args) {
 2         SingleLinkedList<;maJiang> list = new SingleLinkedList<MaJiang>();
 3         list.add(new MaJiang(7, 1));
 4         list.add(new MaJiang(9, 1));
 5         list.add(new MaJiang(9, 3));
 6         list.add(new MaJiang(6, 3));
 7         list.add(new MaJiang(9, 2));
 8         list.add(new MaJiang(1, 3));
 9         list.add(new MaJiang(4, 1));
10         list.add(new MaJiang(2, 1));
11         list.add(new MaJiang(1, 1));
12         list.add(new MaJiang(3, 1));
13         list.add(new MaJiang(9, 3));
14         list.add(new MaJiang(5, 3));
15         list.add(new MaJiang(6, 2));
16         list.add(new MaJiang(8, 2));
17         list.add(new MaJiang(9, 3));
18         
19         System.out.print("n初始数据: ");
20         for (int i = 0; i < list.size(); i++) {
21             System.out.print(list.get(i).toString()+" ");
22         }
23         radixSort(list);
24         System.out.print("n二次排序: ");
25         for (int i = 0; i < list.size(); i++) {
26             System.out.print(list.get(i).toString()+" ");
27         }
28         //测试向指定位置插入数据
29         list.add(5, new MaJiang(8, 3));
30         System.out.print("n在index=5处插入: ");
31         for (int i = 0; i < list.size(); i++) {
32             System.out.print(list.get(i).toString()+" ");
33         }
34         list.add(0, new MaJiang(6, 6));
35         System.out.print("n在index=0插入: ");
36         for (int i = 0; i < list.size(); i++) {
37             System.out.print(list.get(i).toString()+" ");
38         }
39         list.add(3, new MaJiang(3, 3));
40         System.out.print("n在index=3插入: ");
41         for (int i = 0; i < list.size(); i++) {
42             System.out.print(list.get(i).toString()+" ");
43         }
44         
45         list.add(20, new MaJiang(20, 20));
46         System.out.print("n在index=20处插入: ");
47         for (int i = 0; i < list.size(); i++) {
48             System.out.print(list.get(i).toString()+" ");
49         }
50 
51         System.out.print("n: "+ list.get(5).toString());
52         System.out.print("n: "+ list.get(0).toString());
53         System.out.print("n: "+ list.get(18).toString());
54 
55     }

结果如下

@H_512_1357@

 

脚本宝典总结

以上是脚本宝典为你收集整理的从零开始学算法--自定义单链表全部内容，希望文章能够帮你解决从零开始学算法--自定义单链表所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。
标签：javalinkedlistlistloadloadphppythonsortString二次排序排序排序查找查找程序员程序员算法算法遍历遍历
猜你在找的心得技巧相关文章
其他相关热搜词更多
phpjavapython程序员loadpost-format-gallerydivString参数开发ListcapMapClass工具安装SQL数据库资源this
全站导航更多
html5HTML/XhtmlCSSXML/XSLTDreamweaver教程Frontpage教程心得技巧JavaScriptASP.NETPHP编程正则表达式AJAX相关ASP编程JSP编程编程10000问CSS/HTMLFlexvbsDOS/BAThtahtcpythonperl游戏相关VBA远程脚本ColdFusionMsSqlMysqlmariadboracleDB2mssql2008mssql2005SQLitePostgreSQLMongoDB星外虚拟主机华众虚拟主机Linuxwin服务器FTP服务器DNS服务器Tomcatnginxzabbix云和虚拟化bios系统安装系统系统进程Windows系列LINUXRedHat/CentosUbuntu/DebianFedoraSolaris红旗Linux建站经验微信营销网站优化网站策划网络赚钱网络创业站长故事alexa域名photoshop教程摄影教程Fireworks教程CorelDraw教程Illustrator教程Painter教程Freehand教程IndesignSketch笔记本主板内存CPU存储显卡显示器光存储鼠标键盘平板电脑安全教程杀毒防毒安全设置病毒查杀脚本攻防入侵防御工具使用业界动态Exploit漏洞分析
最新心得技巧教程
热门心得技巧教程