Java单链表基本操作的实现

最近被问到链表，是一个朋友和我讨论java的时候说的。说实话，我学习编程的近一年时间里，学到的东西还是挺少的。语言是学了java和c#，关于web的学了一点html+css+javascript。因为比较偏好，学习winform时比较认真，数据库操作也自己有所研究。但链表这个东西我还真没有学习和研究过，加上最近自己在看wpf，而课程也到了jsp了，比较紧。

但是我还是抽了一个晚上加半天的时间看了一下单向链表。并且使用java试着写了一个实例出来。没有接触过链表的朋友可以作为参考，希望大家多提宝贵意见。

我们首先解释一下什么是链表。就我所知，链表是一种数据结构，和数组同级。比如，java中我们使用的arraylist，其实现原理是数组。而linkedlist的实现原理就是链表了。我的老师说，链表在进行循环遍历时效率不高，但是插入和删除时优势明显。那么他有着愈十年的编程经验，我是相信的。不过不知道他是否是说双向链表，我们在此呢只对单向链表做一个了解。

链表（chain本文所说链表均为单向链表，以下均简称单向链表）实际上是由节点（node）组成的，一个链表拥有不定数量的节点。而向外暴露的只有一个头节点（head），我们对链表的所有操作，都是直接或者间接地通过其头节点来进行的。

节点（node）是由一个需要储存的对象及对下一个节点的引用组成的。也就是说，节点拥有两个成员：储存的对象、对下一个节点的引用。

　　这样说可能大家不是很明白，我贴一张图大家可能更容易理解。

java单链表基本操作的实现关键代码如下所示：

package com.tyxh.link; 
//节点类 
public class node { 
protected node next; //指针域 
protected int data;//数据域 
public node( int data) { 
this. data = data; 
} 
//显示此节点 
public void display() { 
system. out.print( data + " "); 
} 
} 
package com.tyxh.link; 
//单链表 
public class linklist { 
public node first; // 定义一个头结点 
private int pos = 0;// 节点的位置 
public linklist() { 
this. first = null; 
} 
// 插入一个头节点 
public void addfirstnode( int data) { 
node node = new node(data); 
node. next = first; 
first = node; 
} 
// 删除一个头结点,并返回头结点 
public node deletefirstnode() { 
node tempnode = first; 
first = tempnode. next; 
return tempnode; 
} 
// 在任意位置插入节点 在index的后面插入 
public void add(int index, int data) { 
node node = new node(data); 
node current = first; 
node previous = first; 
while ( pos != index) { 
previous = current; 
current = current. next; 
pos++; 
} 
node. next = current; 
previous. next = node; 
pos = 0; 
} 
// 删除任意位置的节点 
public node deletebypos( int index) { 
node current = first; 
node previous = first; 
while ( pos != index) { 
pos++; 
previous = current; 
current = current. next; 
} 
if(current == first) { 
first = first. next; 
} else { 
pos = 0; 
previous. next = current. next; 
} 
return current; 
} 
// 根据节点的data删除节点(仅仅删除第一个) 
public node deletebydata( int data) { 
node current = first; 
node previous = first; //记住上一个节点 
while (current. data != data) { 
if (current. next == null) { 
return null; 
} 
previous = current; 
current = current. next; 
} 
if(current == first) { 
first = first. next; 
} else { 
previous. next = current. next; 
} 
return current; 
} 
// 显示出所有的节点信息 
public void displayallnodes() { 
node current = first; 
while (current != null) { 
current.display(); 
current = current. next; 
} 
system. out.println(); 
} 
// 根据位置查找节点信息 
public node findbypos( int index) { 
node current = first; 
if ( pos != index) { 
current = current. next; 
pos++; 
} 
return current; 
} 
// 根据数据查找节点信息 
public node findbydata( int data) { 
node current = first; 
while (current. data != data) { 
if (current. next == null) 
return null; 
current = current. next; 
} 
return current; 
} 
} 
package com.tyxh.link; 
//测试类 
public class testlinklist { 
public static void main(string[] args) { 
linklist linklist = new linklist(); 
linklist.addfirstnode(20); 
linklist.addfirstnode(21); 
linklist.addfirstnode(19); 
//19,21,20 
linklist.add(1, 22); //19,22,21,20 
linklist.add(2, 23); //19,22,23,21,20 
linklist.add(3, 99); //19,22,23,99,21,20 
linklist.displayallnodes(); 
// node node = linklist.deletefirstnode(); 
// system.out.println("node : " + node.data); 
// linklist.displayallnodes(); 
// node = linklist.deletebypos(2); 
// system.out.println("node : " + node.data); 
// linklist.displayallnodes(); 
// linklist.deletefirstnode(); 
node node = linklist.deletebydata(19); 
// node node = linklist.deletebypos(0); 
system. out.println( "node : " + node. data); 
linklist.displayallnodes(); 
node node1 = linklist.findbypos(0); 
system. out.println( "node1: " + node1. data); 
node node2 = linklist.findbydata(22); 
system. out.println( "node2: " + node2. data); 
} 
}

以上所述是小编给大家介绍的java单链表基本操作的实现，希望对大家有所帮助