关于链表学习

单链表学习总结 

 

百度上定义：单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。

 

1、我的理解为：单链表，顾名思义，就是像一条链子一样的东西。比如一条自行车链子，由一个个的小节串在一起，链表也是由一个个称为节点的东西组成。

  但他也被一个称之为“表”，所以也是像所有表格一样可以“填写”或“放置”一些数据的容器。

 

2、链表的节点，通常用 node 单词来表示。并且链表的第一个节点，我们称之为根节点，用root表示。

   链表节点的大致结构也如下图所示

    ┌───┬───┐

     | data    next | 

    └───┴───┘

 

 

   data域------用来存放各种数据的地方

    next域------存放节点的直接后继的地址（位置）的指针域（链域），或者说就是像自行车链的一个小节要

和另一个节接上的扣一样，指向后面的那个小节。

 

3、链表和数组都可以存放数据，但是其显著不同在于

   1：数组一旦定义了，长度就不可以改变，所能存储的东西也就有限。

      而链表像自行车链子一样，可以拆，也可以加，无论是头尾还是中间，都可以对他进行更改。

   2：访问数据时，数组相对快捷，但链表则比较复杂。

 

4、实现链表代码。简单的学生信息的存储。实现添加，索引删除，数据删除，修改，查找，插入，给学生分数排序等功能。

 

 第一步：定义一个节点类；

 

/**
 * 节点类
 * @author 
 *节点node，节点内存储students对象 ,节点指向next 
 */
public class Node {

	public Node(Students stu) {//声明一个节点，里面存储的是学生数据
		this.stu = stu;
	}

	public  Students stu;//数据
	
	public Node next;//引用，指向下一个节点
	
}

 

 第二步，定义一个学生对象，存储学生的姓名和分数信息；

 

/**
 * 定义Student学生类
 * 学生的属性，构造方法，get,set方法
 */
public class Students {
 
private String name;//声明姓名属性
private int score;//声明学分属性
 
/**
* 构造方法，用来创建对象的（类名 对象名 = new 构造方法(参数值,...);）
*/
public Students(String name,int score){
this.name = name;
this.score = score;
}
/**
* 给姓名属性设置值的方法
* @param name要赋给属性的参数
*/
public void setName(String name){
this.name = name;
}
/**
* 获取姓名属性值的方法
* @return name姓名属性的值
*/
public String getName(){
return name;
}
 
public void setScore(int score){
this.score = score;
}
 
public int getScore(){
return score;
}
/**
* 重写一个toString方法
*/
public String toString(){
return "姓名："+name+"   学分："+score;
}
 
}
 

 

第三步，创建一个链表类；

 

/**
 * 链表类
 * 
 * @author 头节点，尾节点，节点总数 链表加减索引插入修改等方法
 */
public class LinkedList {
 
private Node root;// 头节点
private Node rear;// 尾节点
private int size;// 记录节点总数的计数器
 
/**
* 添加节点到链表中的方法
* 
* @param node要被添加的新节点
* @param stu是链表内存储的数据
*/
public void add(Students stu) {
Node node = new Node(stu);
if (root == null) {// 表示第一次添加节点
root = node;
rear = node;
} else {
rear.next = node;
rear = node;// 新的节点成为尾节点
}
size++;
}
 
/**
* 
* 索引指定位置的节点
* 
* @param index为索引的位置
* @return 返回节点内的数据
*/
public Students get(int index) {// 索引
if (index < 0 || index >= size) {
throw new RuntimeException("索引越界！");
}
if (index == 0) {
return root.stu;
}
Node node = root;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node.stu;
}
 
/**
* 
* 移除索引位置的节点
* 
* @param index索引位置
* @return 返回移除的节点数据
*/
public Students remove(int index) {// 移除
if (index < 0 || index >= size) {
throw new RuntimeException("索引越界！");
}
if (index == 0) {
Node node = root;
Node temp = node.next;
root = temp;
 
size--;
return node.stu;
} else {
Node node = root;
for (int i = 0; i < index - 1; i++) {
node = node.next;
}
Node temp = node.next;
Node mode = temp.next;
node.next = mode;
size--;
return temp.stu;
}
}
 
/**
* 
* 插入节点node
* 
* @param stu需要插入的节点数据
* @param index需要插入的位置
*/
public void Charu(Students stu, int index) {// 在索引位置插入节点
if (index < 0 || index > size) {
throw new RuntimeException("索引越界！");
}
Node node = new Node(stu);
if (index == 0) {
Node temp = root;
root = node;
node.next = temp;
} else {
Node node1 = root;
 
for (int i = 0; i < index - 1; i++) {
node1 = node1.next;
}
Node temp = node1.next;
node1.next = node;
node.next = temp;
}
size++;
}
 
/**
* 
* 查找指定的数据所处的位置
* 
* @param stu为指定数据
* @return 返回数据所处的位置j
*/
public int get(Students stu) {// 查找相应的节点所在位置
int j = 0;
Node node = root;
for (int i = 1; i < size; i++) {
node = node.next;
if (stu.getName() == node.stu.getName()
&& stu.getScore() == node.stu.getScore()) {
j = i;
}
}
return j;
}
 
/**
* 修改指定数据的方法
* 
* @param stu1指定的数据
* @param stu2用来替换的数据
*/
public void Xiugai(Students stu1, Students stu2) {// 修改指定位置的节点
int j = get(stu1);
remove(j);
Charu(stu2, j);
}
 
/**
* 交换两个节点所在的位置
* 
* @param stu1
* @param stu2
* 
*/
public void Jiaohuan(Students stu1, Students stu2) {
int i = get(stu1);
int j = get(stu2);
remove(i);
Charu(stu2, i);
remove(j);
Charu(stu1, j);
}
 
/**
* 获取链表中元素总数的方法
* 
* @return 返回size
*/
public int size() {
return size;
}
 
}
 

 

第四步：创建一个链表测试类；

 

/**
 * 链表测试类
 * 
 * @author 输出检验前面的方法
 */
public class ListTest {
 
public static void main(String[] args) {
// 创建链表对象
LinkedList list = new LinkedList();
 
list.add(new Students("张三", 70));
list.add(new Students("李四", 60));
list.add(new Students("王五", 77));
list.add(new Students("小雅", 68));
list.add(new Students("李明", 91));
 
// 检验添加方法
System.out.println();
System.out.println("增加后长度为" + list.size());
System.out.println("增加后为" );
for (int i = 0; i < list.size(); i++) {
Students stu = list.get(i);
System.out.println( stu.toString());
}
 
// 检验交换方法
list.Jiaohuan(list.get(0), list.get(1));
System.out.println();
System.out.println("交换后" );
for (int i = 0; i < list.size(); i++) {
Students stu = list.get(i);
System.out.println( stu.toString());
}
 
// sort排序
for (int i = 0; i < list.size(); i++) {
for (int j = i; j < list.size(); j++) {
if (list.get(i).getScore() < list.get(j).getScore()) {
list.Jiaohuan(list.get(i), list.get(j));
}
}
}
 
// 得出排序情况
System.out.println();
System.out.println("排序后" );
for (int i = 0; i < list.size(); i++) {
System.out.println( list.get(i).toString());
}
 
// 检验删除方法
list.remove(0);
System.out.println();
System.out.println("删除后长度为" + list.size());
System.out.println("删除后为" );
for (int i = 0; i < list.size(); i++) {
Students stu = list.get(i);
System.out.println( stu.toString());
}
// 检验插入方法
list.Charu(new Students("阿黄", 90), 0);
System.out.println();
System.out.println("插入后长度为" + list.size());
System.out.println("插入后为" );
for (int i = 0; i < list.size(); i++) {
Students stu = list.get(i);
System.out.println( stu.toString());
}
// 检验修改方法
list.Xiugai(new Students("阿黄", 90), new Students("小明", 90));
System.out.println();
System.out.println("修改后" );
for (int i = 0; i < list.size(); i++) {
Students stu = list.get(i);
System.out.println( stu.toString());
}
}
 
}

 

 

 the end：

这段时间学习链表，自己似乎走了许多弯路。跌跌撞撞用了一个星期，才稍微摸清了苗头。

其实也知道并不是难，只是在第一次接触链表的那堂课，自己没有好好的接收一些知识，满心以为课后有了百度就完事大吉了。

结果在自己自以为完全搞明白了一些东西之后，却被指出根本思维是不正确的。

 

突然就想起了曾经一个学姐说过的一句话,没有很明显的联系，只是突然的想起吧。

“在做完一道阅读题后，对答案发现自己全错了。然后用半个小时说服了自己，试着去理解参考答案的思维。可到自己认为已经完全搞懂了为什么会错之后，却发现............是自己看错了参考答案，而原先自己的答案实际上全部正确。”

 

 

Finally , learn to walk before you run.

 

评论

1 楼 java--hhf 2014-11-09  

好详细呀 膜拜一下