【数据结构】Java语言描述-单链表的基本操作

单链表是数据结构中以动态结构存储的线性结构，在Java语言中，一般用本类对象引用的方式在内存中将一组相同类型的对象存储，熟悉单链表的基本操作有助于灵活解决此类算法问题。

1.单链表中的节点可以用节点类型描述如下：

public class Lnode{
    public char data;
    public Lnode next;
}

2.单链表可以按如下的类进行封装：

public class LinkedList{
    Lnode h = null;
    public LinkedList(){...}
    public insertElement(char ch,int i){...}
    //...省略方法
}

3.头插法建立单链表

public LinkedList(String str){
    h = new Lnode;
    h.next = null;
    int i = 0;
    Lnode p;
    char ch;
    while(i<str.length()){
        ch = str.charAt(i);
        p = new Lnode();
        p.data = ch;
        p.next = h.next;
        h.next = p;
        i++;
    }
}

4.尾插法建立单链表

public LinkedList(String str){
    h = new Lnode();
    h.next = null;
    char ch;
    Lnode p;
    Lnode t = h;
    int i = 0;
    while(i<str.length()){
        ch = str.charAt(i);
        p = new Lnode;
        p.data = ch;
        p.next = null;
        t.next = p;
        t = p;
        i++;
    }
}

5.求单链表的长度

public int size(){
    int i = 0;
    Lnode p = h.next;
    while(p!=null){
        i++;
        p = p.next;
    }
    return i;
}

6.1 在单链表某节点之后插入新节点

public void insertElementAfter(Lnode p,char ch){
    Lnode s = new Lnode();
    s.data = ch;
    s.next = p.next;
    p.next = s;
}

6.2 在单链表第i个元素之前插入一个元素

public int insertElementAt(int i,char ch){
    Lnode p;
    int k = 0;
    p = h.next;
    while(p!=null&&k<i-1){
        p = p.next;
        k++;
    }
    if(p!=null){
        Lnode s = new Lnode();
        s.data = ch;
        s.next = p.next;
        p.next = s;
        return 1;
    }
    return 0;
}

7.删除单链表中某节点的后继节点

public void remove(Lnode p){
    if(p.next!=null){
        Lnode s = p.next;
        p.next = s.next;
        s = null;
    }
}

8.1 按值查找

public Lnode search(char ch){
    Lnode p = h.next;
    while(p!=null&&p.data!=ch){
        p = p.next;
    }
    return p;
}

8.2 按位置查找

public Lnode get(int i){
    Lnode p = h.next;
    int k = 0;
    while(p!=null&&k<i){
        p = p.next;
        k++;
    }
    if(i==k)
        return p;
    else
        return null;
}