|
最近被问到链表，是一个朋友和我讨论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 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 } 以上的代码就是一般链表的骨架了。拥有两个重要属性。 那么做为能添加到链表的节点又该长什么样子呢？ 我们可以写作如下： 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 name 108 * 对象姓名 109 * @return 对象数组，可能多个 110 */ 111 public Person[] searchNodeByPersonName(String name) { 112 return null; 113 } 114 115 /** 116 * 通过年龄查找对象 117 * 未实现 118 * @param age 119 * 对象年龄 120 * @return 对象数组，可能多个 121 */ 122 public Person[] searchPersonByAge(int age) { 123 return null; 124 } 125 126 /** 127 * 通过编号查找对象 128 * 由于编号是唯一标识，循环遍历查找并返回即可 129 * @param personNo 130 * 对象编号 131 * @return 查找到的对象或者null 132 */ 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 personNo 147 * 要修改的对象编号 148 * @param value 149 * 通过传入值的类型判断修改 只能修改姓名或年龄 150 */ 151 public void editNode(int personNo, Object value) { 152 // 通过作为唯一标识的编号查找到对象 153 Person target = searchNode(personNo); 154 if (target == null) { // 如果对象为null 155 return; 156 } 157 if (value == null) { // 如果传入参数为null 158 return; 159 } 160 // 如果传入参数为字符串类型 161 if (value.getClass() == java.lang.String.class) { 162 target.name = value.toString(); 163 return; 164 } 165 try { 166 // 如果传入参数为整型 167 target.age = Integer.parseInt(value.toString()); 168 return; 169 } catch (Exception ex) { 170 // 如果传入参数类型错误 171 return; 172 } 173 } 174 175 /** 176 * 通过对象编号打印对象 177 * 178 * @param personNo 179 * 对象编号 180 */ 181 public void printNode(int personNo) { 182 Person target = searchNode(personNo); 183 if (target == null) { 184 return; 185 } 186 System.out.println(target.toString()); 187 } 188 189 /** 190 * 判断指定对象是否存在链表中 191 * 192 * @param personNo 193 * 对象编号 194 * @return true表示存在该对象，false表示不存在该对象 195 */ 196 public boolean contains(int personNo) { 197 if (size != 0) { 198 for (PersonChainNode pcn = head; pcn != null; pcn = pcn.nextNode) { 199 if (pcn.person.personNo == personNo) { 200 return true; 201 } 202 } 203 } 204 return false; 205 } 206 207 // 排序方法 208 209 /** 210 * 通过姓名排序 211 */ 212 public void sortByPersonName() { 213 } 214 215 /** 216 * 通过年龄排序 217 */ 218 public void sortByPersonAge() { 219 } 220 221 /** 222 * 默认排序，通过编号排序 223 * 使用冒泡排序，增加了判断以提高效率 224 */ 225 public void sort() { 226 boolean jx = true; // 冒泡排序的简化方法 227 for (PersonChainNode pcn = head; pcn != null && jx; pcn = pcn.nextNode) { 228 jx = false; 229 for (PersonChainNode pc = head; pc != null && pc.nextNode != null; pc = pc.nextNode) { 230 if (pc.person.personNo > pc.nextNode.person.personNo) { 231 Person temp = pc.person; 232 pc.person = pc.nextNode.person; 233 pc.nextNode.person = temp; 234 jx = true; 235 } 236 } 237 } 238 } 239 240 /** 241 * 打印整个链表 242 */ 243 public void printAll() { 244 if (size != 0) { 245 for (PersonChainNode pcn = head; pcn != null; pcn = pcn.nextNode) { 246 System.out.println(pcn.person.toString()); 247 } 248 } 249 } 250 }  2012-04-11 21:33:32 那么实际上呢，我们在Java编程中使用的LinkedList就是在其内部维护着一个链表。 实际上的操作不外乎增删改查，不同的是由于高度封装，Jdk的LinkedList是使用索引来取得对象并进行操作的。 和以上我的例子是不尽相同的，因为我是安全按照自己的需求来做的，这样比较简单，实际上为了代码重用复用和扩展。Jdk内的链表节点不知道保存的信息，因此没有办法以除了索引之外的方式获取元素。
今天课程到了Java集合框架，老师略微提了一下单向不循环链表。 我将老师的举例改编一下，帮助大家理解： 老师需要找某一个同学，但是碰巧实在放假的时间内。同学们所处的位置都不一样。老师知道班长的手机号码，所以老师打电话给了班长，班长说他也不知道，但是他知道'我'的电话，他又打给我，我也不知道那位同学的地址，我又继续向下一个同学打电话，直到找到他。 那么在以上示例中，加入每一个同学都有另一个同学的电话（有且仅有一个）。 我们就可以说符合单向链表的环境了。大家可以理解记忆。
大家都知道，我们所创建的对象是保存在内存中的。数组是如此，链表也是如此。 但是数组是一个整体空间，所有元素共用。就比如教室内上课的同学们。教室的容量是固定的，同学可少不可多，老师若希望进行查询，能够一眼看出来。 链表和其节点是不同的存储位置，比如我们一个班毕业了。有的同学去了国外，有的去了北京。大家的位置不同，但是有一定联系的。
2012-04-23 19:16:20
|
|
|
