单向链表的实现（增删查改...）

        写一个大家都比较熟悉的数据结构：单向链表。

   不过先告诉大家一个小秘密，java的API里面已经提供了单向链表的类，大家可以直接拿来用，不过学习数据结构课程的时候想必大家也已经知道，虽然系统会给我们提供一些常用的数据结构，但是自定义的总是能够带来不同的喜感的，而且通过自己的编写也更能够让我们了解其中实现的过程，而且我们还可以写一些比较个性化的方法作为属于自己的数据结构。这里主要是介绍一些常用结构里面都会用到的方法，以及链表具体是如何操作的。

       首先，单链表相对于队列的优势在于存储地址不是连续的，这样的意义在于，操作其中的某一个位置的元素时不需要对之前的其他元素都进行内存操作，大大的为我们的计算机减压了。下面直接进入正题：

       先要定义一个结点类，如下：

 

public class Node {
		Node next;//下一个结点的引用
		Object obj;//结点元素
		public Node(Object obj){
			this.obj=obj;
		}
}

 

       然后就是我们的LinkedList类，先要定义一个空链表：

    Node head=null;//创建一个空链表,头结点

    Node last=head;//尾结点

       打印链表有两种方法，可以采用递归，也可以使用非递归的方法，如下：

 

/**
* 非递归打印元素的方法
*/
public void print(Node head){
	while(head!=null){
		System.out.println(head.obj);
		head=head.next;//索引向后移位
	}
}
/**
 * 递归打印链表元素的方法
 */
public void printNode(Node head){
	if(head!=null){
		System.out.println(head.obj);
		Node node=head.next;
		printNode(node);//递归调用
	}
}

       非递归方法有一个致命的缺陷，打印的同时改变了头结点的位置，所以我们应该倾向于使用递归方法。

       说了这么多，增删查改正式开始：

       向链表中添加元素。判断一个链表已经到达末尾的依据是该结点的next引用已经为Null,所以要向末尾添加一个结点，先要把新增结点放在最后，再把末尾结点向后移位，具体操作过程如下图：

      

       代码如下：

      

/**
 * 向指定链表添加元素的方法
 * @param obj	插入的元素
*/
public void add(Object obj){
	Node node=new Node(obj);//新建结点 
	if(head==null){//如果链表为空
		head = node;
	}else{
		last.next=node;//先把新增结点放在最后
	}
	last=node;//再把最后一个结点向后移位
}

 

       插入元素。要插入一个新元素首先要创建一个新结点来存放它，而在具体实现的时候最让人头疼的时候无疑是怎样找到指定位置的索引了，这里所说的方法在下面的其他操作基本上都是这样衍生的，先了解一下插入结点的具体实现，根据这个结构的逻辑定义，如果我们要在结点A之后插入一个结点，那么就还需要修改结点A的next引用，实际上就是让A结点的next引用指向新增结点的元素域，然后再让新增结点的next引用指向A原本next结点(B)的元素域，用图来表示更加直观：

 

 

       代码如下：

 

/**
 * 向链表中插入新元素的方法	
*/
public void insert(int index,Object obj){
	Node node=head;
	int j=0;
	while(node!=null&&j<index-2){
		//查找到第index-1个元素
		node=node.next;
		j++;
	}
	Node sert=new Node(obj);//被插入的结点
	sert.next=node.next;
	node.next=sert;
}

       删除元素。知道了插入元素的具体操作之后，删除元素就显得相对简单了，比如说我们要删除一个结点b，就是要使这个结点失去引用，但是注意不要直接写b=b.next,这样的话b的引用还是存在，而且还会出现另一种错误，大家可以自己试一下，如图所示，正确的删除结点的方法如下：

 

 

       代码如下：

 

/**
 * 删除指定位置的结点
 * @param index 索引
 */
public void delete(int index){
	Node node=head;
	int j=0;
	while(node!=null&&j<index-2){
		//查找到第i-1个元素
		node=node.next;
		j++;
	}
	node.next=node.next.next;//删除第index个元素
}

 

       最后就是修改元素了。相信大家看完之前的两个方法，接下来的这个方法在心中早就已经泛起波澜了吧，那下面就直接贴代码了：

 

/**
* 改变指定位置的元素
 * @param index 索引
 * @param obj	
 */
public void modify(int index,Object obj){
	Node node=head;
	int j=0;
	while(node!=null&&j<index-1){
		//找到第index个结点
		node=node.next;
		j++;
	}
	node.obj=obj;
}

 

    当然，除了这些基本操作，我们还可以写获取链表长度的方法，获取指定位置的元素的方法等等，这里就不一一介绍了，主要是让大家熟悉一下这个数据结构。最近一阵学校课程太多，心里有很多想法却一直开不了口啊，慢慢来吧，学习也不是一天两天的事情，这几天都没搞锻炼了，今天在教室考试的时候就有人突然癫痫犯了，做技术的更应该关注自己的身体，加油。。。

评论

8 楼 fxrz12 2013-05-16  

基础算法相关的这些前人们已经完善好十几年了，所以都形成了固有工具，并经过了无数次地检验，包过高效，你打算了解他的原理是个很不错的学习方法，可惜时间还是花错方向，是方向错了，诚然你不到20岁，可学习的东西时刻都在变化，一年不学新的就落伍，而你学的这些连培训都不讲，若按照你现在的学习，估计刚学完3年，新的技术又够你学习3年。

7 楼 cq520 2013-05-07  

fxrz12 写道

学c或者c++ 链表是要学和懂得，学JAVA重点是面向对象，以及相关的各种框架及工具。你OUT了！还不是一点点，这篇博文是浪费时间的行为，楼主好自为之。

   楼主现在还没20岁，我的青春还有很多时间可以学习很多东西，我相信一年后写出的东西绝对比现在优质的多，技能的熟练只是一个时间的问题，但是技巧的提升却不是那么容易的。这篇博客面向的对象也不是大神级的人物，只是让大家了解链表的实现过程，许多东西java框架中都有实现，一种方法用上100多遍总能生巧，但是什么时候你能自己写个更优的方法替代它？？？

6 楼 fxrz12 2013-05-07  

学c或者c++ 链表是要学和懂得，学JAVA重点是面向对象，以及相关的各种框架及工具。你OUT了！还不是一点点，这篇博文是浪费时间的行为，楼主好自为之。

5 楼 jsjxqjy 2013-04-25  

嗯,现在就业压力大,早点接触学习好点.

4 楼 cq520 2013-04-25  

jsjxqjy 写道

嗯,对自己学习单向链表数据结构还是有用的.

真心想知道,Java是自学的还是有老师指导?

现在在外面参加培训，学校还没有开始上java的课程，一些知识点如果存在错误，还望大家不吝赐教。

3 楼 jsjxqjy 2013-04-25  

嗯,对自己学习单向链表数据结构还是有用的.

真心想知道,Java是自学的还是有老师指导?

2 楼 cq520 2013-04-25  

感谢回复中提到的泛型定义的方法，这里使用是对象类型，以后再跟大家一起来探讨一下泛型

1 楼 ssyujay 2013-04-25  

public class Node<T> {  
        Node next;//下一个结点的引用  
             T obj;//结点元素  
        public Node(T obj){  
            this.obj=obj;  
        }  
}