本篇文章主要介紹針對單連結清單的基本操作，包括前期的建立順序連結清單，插入及删除的實作，最後是對單連結清單的周遊，代碼基于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");
}
}
測試結果：