首页 > 代码库 > 【转】单向链表(单链表)的Java实现
【转】单向链表(单链表)的Java实现
最近被问到链表,是一个朋友和我讨论Java的时候说的。说实话,我学习编程的近一年时间里,学到的东西还是挺少的。语言是学了Java和C#,关 于Web的学了一点Html+css+javascript。因为比较偏好,学习WinForm时比较认真,数据库操作也自己有所研究。但链表这个东西我 还真没有学习和研究过,加上最近自己在看WPF,而课程也到了JSP了,比较紧。
但是我还是抽了一个晚上加半天的时间看了一下单向链表。并且使用Java试着写了一个实例出来。没有接触过链表的朋友可以作为参考,希望大家多提宝贵意见。
当然,我们首先解释一下什么是链表。就我所知,链表是一种数据结构,和数组同级。比如,Java中我们使用的ArrayList,其实现原理是 数组。而LinkedList的实现原理就是链表了。我的老师说,链表在进行循环遍历时效率不高,但是插入和删除时优势明显。那么他有着愈十年的编程经 验,我是相信的。不过不知道他是否是说双向链表,我们在此呢只对单向链表做一个了解。
链表(Chain本文所说链表均为单向链表,以下均简称单向链表)实际上是由节点(Node)组成的,一个链表拥有不定数量的节点。而向外暴露的只有一个头节点(Head),我们对链表的所有操作,都是直接或者间接地通过其头节点来进行的。
节点(Node)是由一个需要储存的对象及对下一个节点的引用组成的。也就是说,节点拥有两个成员:储存的对象、对下一个节点的引用。
这样说可能大家不是很明白,我贴一张图大家可能更容易理解。
那么大家可能清除了,为什么说有了头节点就可以操作所有节点。因为有着不断的引用嘛!
那么在链表里的属性大概就只有两个了:头节点和节点数量。当然,根据需要,我们通常需要更多的属性。
简单的链表可以写为下面的样子:
1 package myChain; 2 3 /** 4 * (单向)链表 5 * 6 * @author Johness 7 */ 8 public class PersonChain { 9 private PersonChainNode head; // 头节点10 private int size; // 链表的实体(即节点的数量)11 private int modCount; // 链表被操作的次数(备用)12 13 /**14 * 获得链表中节点数量15 * 16 * @return 链表中节点数17 */18 public int getSize() {19 return this.size;20 }21 22 /**23 * 添加节点的一般方法24 * 25 * @param p26 * 添加到链表节点的对象 由于实现细节,作为唯一标识,同一个编号的Person只能添加一次27 */28 public void addNode(Person p) {29 if (!contains(p.personNo)) { // 如果链表中没有该对象,则准备添加30 if (head != null) { // 如果有头节点,则添加新节点作为头节点31 head = new PersonChainNode((myChain.Person) p, head);32 size++;33 modCount++;34 } else { // 如果没有头节点,则添加对象作为头节点35 head = new PersonChainNode((myChain.Person) p, null);36 size++;37 modCount++;38 }39 }40 }41 }
以上的代码就是一般链表的骨架了。拥有两个重要属性。
那么做为能添加到链表的节点又该长什么样子呢?
我们可以写作如下:
1 package myChain; 2 3 /** 4 * (节点)实体,封装了‘人‘这个对象和下一个实体的引用 5 * 该实体将作为(单向)链表的节点 6 * @author Johness 7 */ 8 public class PersonChainNode { 9 Person person; // 人10 PersonChainNode nextNode; // 该对象(‘人‘)保存的下一个对象的引用11 12 // 获取当前实体对象(‘人‘)13 public Person getPerson(){14 return this.person;15 }16 17 // 获取下一个实体18 public PersonChainNode getNextNode(){19 return this.nextNode;20 }21 22 // 构造方法23 public PersonChainNode (Person p,PersonChainNode ep){24 this.person = p;25 this.nextNode = ep;26 }27 }
当然了,这只是个大概的样子。
那么我最后在把层次梳理一下:链表是由不定数量的节点连接(通过相互之间的引用)起来的,由于这种关系,在链表里我们只定义了头节点和节点数量。节点是由存储的对象及对下一个“节点”的引用封装而成。
在添加节点到链表中时,首先添加的节点后置后,新添加的节点作为头节点引用前一个添加的节点。
废话不多说,贴上我的例子,老师说我废话多……
(以下的例子较为简陋,大家不要笑话我哈)
1 package myChain; 2 3 /** 4 * ‘人‘ 类 5 * @author Johness 6 * @version 1.0 7 */ 8 public class Person { 9 String name; // 姓名10 int age; // 年龄11 int personNo; // 编号,用作唯一标识12 13 // 带参构造方法14 public Person(String name, int age, int personNo) {15 this.name = name;16 this.age = age;17 this.personNo = personNo;18 }19 20 // 获取姓名21 public String getName(){22 return this.name;23 }24 25 // 获取年龄26 public int getAge(){27 return this.age;28 }29 30 // 获取编号31 public int getPersonNo(){32 return this.personNo;33 }34 35 // 用于输出的信息36 public String toString(){37 return "姓名:" + this.name + "\t年龄:" + this.age +"\t编号" + this.personNo;38 }39 }
1 package myChain; 2 3 /** 4 * (节点)实体,封装了‘人‘这个对象和下一个实体的引用 5 * 该实体将作为(单向)链表的节点 6 * @author Johness 7 */ 8 public class PersonChainNode { 9 Person person; // 人10 PersonChainNode nextNode; // 该对象(‘人‘)保存的下一个对象的引用11 12 // 获取当前实体对象(‘人‘)13 public Person getPerson(){14 return this.person;15 }16 17 // 获取下一个实体18 public PersonChainNode getNextEntity(){19 return this.nextNode;20 }21 22 // 构造方法23 public PersonChainNode (Person p,PersonChainNode ep){24 this.person = p;25 this.nextNode = ep;26 }27 28 // 构造方法29 public PersonChainNode (Person p){30 this.person = p;31 }32 }
1 package myChain; 2 3 /** 4 * (单向)链表 5 * 6 * @author Johness 7 */ 8 public class PersonChain { 9 private PersonChainNode head; // 头节点 10 private int size; // 链表的实体(即节点的数量) 11 private int modCount; // 链表被操作的次数(备用) 12 13 /** 14 * 获得链表中节点数量 15 * 16 * @return 链表中节点数 17 */ 18 public int getSize() { 19 return this.size; 20 } 21 22 /** 23 * 添加节点的一般方法 24 * 25 * @param p 26 * 添加到链表节点的对象 由于实现细节,作为唯一标识,同一个编号的Person只能添加一次 27 */ 28 public void addNode(Person p) { 29 if (!contains(p.personNo)) { // 如果链表中没有该对象,则准备添加 30 if (head != null) { // 如果有头节点,则添加新节点作为头节点 31 head = new PersonChainNode((myChain.Person) p, head); 32 size++; 33 modCount++; 34 } else { // 如果没有头节点,则添加对象作为头节点 35 head = new PersonChainNode((myChain.Person) p, null); 36 size++; 37 modCount++; 38 } 39 } 40 } 41 42 /** 43 * 通过编号删除对象 44 * 45 * @param personNo 46 * 要删除对象的编号 47 */ 48 public void deleteNode(int personNo) { 49 if (size == 0) { // 如果当前链表节点数为零 50 return; 51 } 52 if (size == 1) { 53 // 如果只有一个节点并且正是需要删除的对象 54 if (head.person.personNo == personNo) { 55 head = null; 56 size = 0; 57 } 58 return; 59 } 60 // 如果不存在该对象编号 61 if (!contains(personNo)) { 62 return; 63 } 64 65 // 较为复杂的删除,定义整型保存被删除的节点的索引 66 //(删除和索引都是不存在的,这里只是一个说法) 67 int index = 0; 68 // 循环遍历,找到删除节点的索引 69 for (PersonChainNode p = head; p != null; p = p.nextNode) { 70 if (!(p.person.personNo == personNo)) { 71 index++; 72 } else { 73 break; 74 } 75 } 76 // 如果删除的是第一个节点(即头节点) 77 if (index == 0) { 78 head = new PersonChainNode(head.nextNode.person, 79 head.nextNode.nextNode); // 设置头节点后一个节点为新的头节点 80 size--; // 链表节点数减一 81 modCount++; // 链表被操作次数加一 82 return; 83 } 84 85 // 如果删除的节点不是第一个节点 86 // 循环遍历,找到被删除节点的前一个节点 87 // 其索引下标用count保存 88 int count = 0; 89 for (PersonChainNode p = head; p != null; p = p.nextNode) { 90 if (count == index - 1) { // 如果找到了被删除节点的前一个节点 91 if (index == size - 1) { // 如果被删除节点是最后一个节点 92 p.nextNode = null; // 将被删除节点的前一个节点的引用指向空引用 93 } else { // 如果被删除节点不是最后一个节点 94 p.nextNode = p.nextNode.nextNode; // 将被删除节点前一个节点对其引用指向被删除节点的下一个节点 95 } 96 size--; // 减一数量 97 modCount++; // 加一操作次数 98 return; 99 }100 count++; // 没有找到,索引加一101 }102 }103 104 /**105 * 通过姓名查找对象106 * 未实现107 * @param name108 * 对象姓名109 * @return 对象数组,可能多个110 */111 public Person[] searchNodeByPersonName(String name) {112 return null;113 }114 115 /**116 * 通过年龄查找对象117 * 未实现118 * @param age119 * 对象年龄120 * @return 对象数组,可能多个121 */122 public Person[] searchPersonByAge(int age) {123 return null;124 }125 126 /**127 * 通过编号查找对象128 * 由于编号是唯一标识,循环遍历查找并返回即可129 * @param personNo130 * 对象编号131 * @return 查找到的对象或者null132 */133 public Person searchNode(int personNo) {134 Person p = null;135 for (PersonChainNode pcn = head; pcn != null; pcn = pcn.nextNode) {136 if (pcn.person.personNo == personNo) {137 p = pcn.person;138 }139 }140 return p;141 }142 143 /**144 * 通过原对象修改及传入值修改该对象属性145 * 146 * @param personNo147 * 要修改的对象编号148 * @param value149 * 通过传入值的类型判断修改 只能修改姓名或年龄150 */151 public void editNode(int personNo, Object value) {152 // 通过作为唯一标识的编号查找到对象153 Person target = searchNode(personNo);154 if (target == null) { // 如果对象为null155 return;156 }157 if (value =http://www.mamicode.com/= null) { // 如果传入参数为null>
2012-04-11 21:33:32
那么实际上呢,我们在Java编程中使用的LinkedList就是在其内部维护着一个链表。
实际上的操作不外乎增删改查,不同的是由于高度封装,Jdk的LinkedList是使用索引来取得对象并进行操作的。
和以上我的例子是不尽相同的,因为我是安全按照自己的需求来做的,这样比较简单,实际上为了代码重用复用和扩展。Jdk内的链表节点不知道保存的信息,因此没有办法以除了索引之外的方式获取元素。
今天课程到了Java集合框架,老师略微提了一下单向不循环链表。
我将老师的举例改编一下,帮助大家理解:
老师需要找某一个同学,但是碰巧实在放假的时间内。同学们所处的位置都不一样。老师知道班长的手机号码,所以老师打电话给了班长,班长说他也不知道,但是他知道‘我‘的电话,他又打给我,我也不知道那位同学的地址,我又继续向下一个同学打电话,直到找到他。
那么在以上示例中,加入每一个同学都有另一个同学的电话(有且仅有一个)。
我们就可以说符合单向链表的环境了。大家可以理解记忆。
大家都知道,我们所创建的对象是保存在内存中的。数组是如此,链表也是如此。
但是数组是一个整体空间,所有元素共用。就比如教室内上课的同学们。教室的容量是固定的,同学可少不可多,老师若希望进行查询,能够一眼看出来。
链表和其节点是不同的存储位置,比如我们一个班毕业了。有的同学去了国外,有的去了北京。大家的位置不同,但是有一定联系的。
【转】单向链表(单链表)的Java实现