本篇文章主要介绍针对单链表的基本操作，包括前期的创建顺序链表，插入及删除的实现，最后是对单链表的遍历，代码基于Java语言实现。
1.创建结点
单链表的结点包含两部分，数据域存储相关数据，指针域存储下一个结点的地址，如果没有其值为null，在这里定义一个私有的结点类即可：数据类型可任意指定，示例选用字符串
//结点类
private class Node{
private String str; //数据域
Node next; //指针域
}
特殊结点包括头结点和尾结点，这也是后续进行插入或删除需要考虑的边界条件，为方便处理，提前在链表类中定义出来
private Node first; //头结点
private Node last; //尾结点
private int N; //链表大小
链表判空+大小：
//头结点为空即整个链表为空
public boolean isEmpty() {
return first==null;
}
//返回链表大小
public int size() {
return N;
}
2.顺序添加节点
初始创建链表时需要将所有结点顺序链接起来，实际上涉及到的就是在表尾插入结点（特殊边界条件之一）
插入过程如下：
//在表尾插入结点
Node oldlast=last;
last=new Node();
last.str=line;
oldlast.next=last;
3.查找结点（按值查找）
循环遍历查找即可，按索引查找同理
for(Node x=first;x!=null;x=x.next) {
if(x.str.equals(line)) {
return line;
}
}
4.插入结点
在链表建立成功后进而实现在任意位置插入元素，首先考虑特殊的边界条件，上面已实现在表尾插入节点，这里实现在表头插入结点，实现过程如下
//在表头插入节点
Node oldfirst=first;
first=new Node();
first.str=line;
first.next=oldfirst;
接下来考虑一般情况，在表中插入结点，遍历查找到插入位置的前一个结点，让它指向新插入的结点，新插入的结点指向它原先的后继结点
//在表中插入结点
Node x=first;
while((index--)>2) {
x=x.next;
}
Node n=new Node();
n.str=line;
n.next=x.next;
x.next=n;
5.删除结点
删除结点的话有按值删除和按索引删除两种，二者实现原理相同，这里介绍按索引删除。首先考虑边界条件：
index=1：删除表头结点，令first=first.next;
index=N：删除表尾结点，遍历找到表尾结点的前驱节点，令前驱结点的指针域为null
删除表中的结点，遍历找到所删结点的前驱结点，令前驱结点指向所删结点的后继结点
//删除表中结点
Node x=first;
while((i--)>2) {
x=x.next;
}
x.next=x.next.next;
6.遍历链表
循环遍历输出每一个结点的数据域
完整程序：
package Datastruct;
//单链表
class LinkList{
class Node{
String str;
Node next;
}
private Node first;
private Node last;
private int N;
public boolean isEmpty() {
return first==null;
}
public int size() {
return N;
}
public void clearList() {
first=null;
N=0;
}
public void put(String line) {
Node oldlast=last;
last=new Node();
last.str=line;
if(isEmpty()) first=last;
else oldlast.next=last;
N++;
}
public String search(String line) {
if(isEmpty())
return "Not Exist";
for(Node x=first;x!=null;x=x.next) {
if(x.str.equals(line)) {
return line;
}
}
return "not exist";
}
//将指定元素插入到index位置上，范围为1-N,在表尾插入节点的话直接调用put()方法;
public void insert(int index,String line) {
if(isEmpty()) {
first.str=line;
return;
}
if(index<1||index>N) {
System.out.println("未在链表范围 ，插入失败");
return;
}
//在表头插入结点
if(index==1) {
Node oldfirst=first;
first=new Node();
first.str=line;
first.next=oldfirst;
}
//在表中插入结点
else {
Node x=first;
while((index--)>2) {
x=x.next;
}
Node n=new Node();
n.str=line;
n.next=x.next;
x.next=n;
}
N++;
}
//按值查找删除相应结点
public void deleteLine(String line) {
if(isEmpty()) {
System.out.println("List is empty,delete failed");
return;
}
else if(search(line).equals(line)) {
//删除头结点
if(first.str.equals(line)) {
first=first.next;
}
//删除尾结点
else if(last.str.equals(line)){
Node x;
for(x=first;x!=null;) {
if(x.next.next==null)
break;
else x=x.next;
}
x.next=null;
last=x;
}
//删除中间结点
else {
Node x;
for(x=first;x!=null;x=x.next) {
if(x.next.str.equals(line)) {
x.next=x.next.next;
break;
}
}
}
N--;
}
else {
System.out.println("the delete element not exist");
return;
}
}
//删除第i个结点
public void deleteIndex(int i) {
if(isEmpty()) {
System.out.println("List is Empty,delete failed");
return;
}
if(i<1||i>N) {
System.out.println("delete failed");
return;
}
if(i==1) {
first=first.next;
}
else if(i==N) {
Node x;
for(x=first;x!=null;) {
if(x.next.next==null) {
break;
}
else x=x.next;
}
x.next=null;
last=x;
}
else {
Node x=first;
while((i--)>2) {
x=x.next;
}
x.next=x.next.next;
}
N--;
}
public void show() {
if(isEmpty())
System.out.println("链表为空");
else {
for(Node x=first;x!=null;x=x.next) {
System.out.print(x.str+" ");
}
System.out.println();
}
}
public Node getFirst() {
return first;
}
public Node getLast() {
return last;
}
}
public class LinkListTest {
public static void main(String[] args) {
long start=System.currentTimeMillis();
LinkList s=new LinkList();
s.put("messi");
s.put("barca");
s.put("yrf");
s.insert(1,"lz");
s.show();
System.out.println("链表大小:"+s.size());
String l="barca";
s.deleteLine(l);
s.show();
//System.out.println(s.search(l));
System.out.println("链表大小:"+s.size());
s.deleteIndex(2);
s.show();
System.out.println("链表大小:"+s.size());
s.put("pika");
s.show();
System.out.println("链表大小:"+s.size());
String m="pika";
System.out.println(s.search(m));
//System.out.println(s.getLast().str);
s.clearList();
s.show();
System.out.println(s.size());
long end=System.currentTimeMillis();
System.out.println("time="+(end-start)+"ms");
}
}
测试结果：