Java数据结构——单链表

一、单链表的概念

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。这组存储单元可以是连续的，也可以是不连续的。

存储单元由两部分组成，数据源和指针，数据源放数据，指针指向下个存储单元。

二、单链表的结构

采用Node实体类类标识，其中data为存储的数据，next为下一个结点的指针。

//链表的实体类
class Node{
    public int data;
    public Node next;
    public Node(int data) {
        this.data = data;
    }
}

三、单链表的常见操作

package org.learn.link;

import java.util.Stack;

public class TestList {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        MyLinkedLsit mylist = new MyLinkedLsit();
        mylist.addNodeH(22);
        mylist.addNodeH(32);
        mylist.addNodeH(25);
        mylist.addNodeH(11);
        
        mylist.print();
        System.out.println("链表的长度："+mylist.getLength());
        System.out.println(mylist.findLastIndexNode(mylist.getHead(), 3).data);
        
        mylist.reverseList(mylist.getHead());
        System.out.println("反转的链表：");
        mylist.print();
        System.out.println("栈逆序输出的链表：");
        mylist.reversePrint();
        //mylist.delete(1);
        //mylist.print();
        
    }

}

class MyLinkedLsit{
    
    //初始化头结点（不存放具体数据）
    Node head = new Node(0);
    //返回头结点
    public Node getHead() {
        return head;
    }
    
    //添加结点(尾插法)
    public void addNodeT(int data) {
        Node newnode = new Node(data);//生成新结点
        Node cur = head;//当前结点
        while(cur.next != null) {//找到最后一个结点
            cur = cur.next;
        }
        cur.next = newnode;
    }
    
    //添加结点（头插法）
    public void addNodeH(int data) {
        Node newnode = new Node(data);//生成新结点
        newnode.next = head.next;
        head.next = newnode;
    }
    //获取链表的长度
    public int getLength() {
        int length = 0;
        Node cur = head.next;
        while(cur != null) {
            length++;
            cur = cur.next;
        }
        return length;
    }
    //删除第k个结点
    public void delete(int k) {
        if(k<1 || k>getLength()) {
            System.out.println("待删除的结点不存在");
            return;
        }
        int i = 1;
        Node cur = head;
        while(cur.next != null) {
            if(i == k) {
                cur.next = cur.next.next;
                return;
            }
            else
            {
                cur = cur.next;
                i++;
            }    
        }
    }
    
    //查找链表中倒数第index个结点
    public Node findLastIndexNode(Node head,int index) {
        //判断链表是否为空
        if(head.next == null)
            return null;
        //得到结点
        int size = getLength();
        if(index<1 || index>size) 
            return null;
        Node cur = head.next;
        for(int i=0;i)
            cur = cur.next;
        return cur;
        
    }
    //单链表反转
    public void reverseList(Node head) {
        if(head.next == null || head.next.next == null)//如果链表为空或只有一个结点，无需反转
            return;
        Node cur = head.next;//辅助变量，帮助遍历链表
        Node nextNode = null;//指向当前结点cur的下一个结点
        Node reverseNode = new Node(0);//初始化另一个头结点
        //遍历原来的链表，每遍历一个结点，将其取出，并放到新的链表的最前端
        while(cur!=null) {
            nextNode = cur.next;//暂时保存当前结点的下一个结点
            cur.next = reverseNode.next;//将cur的下一个结点指向新的链表的最前端
            reverseNode.next = cur;//将cur连接到新的链表
            cur = nextNode;//cur后移
        }
        head.next = reverseNode.next;//将头节点指向另一个头节点，实现单链表的反转
        
    }
    
    //逆序打印单链表（不用反转，利用栈）
    public void reversePrint() {
        if(head.next == null)
            return;
        //Stack stack = new Stack();
        Stack stack = new Stack();
        Node cur= head.next;
        //将链表中所有结点压入栈中
        while(cur!=null) {
            stack.push(cur.data);
            cur = cur.next;
        }
        //将栈中的结点进行打印
        while(stack.size() >0)
            System.out.print(stack.pop()+" ");//栈的特点是先进后出
    }
    //显示结点
    public void print() {
        Node cur = head.next;
        while(cur != null) {
            System.out.print(cur.data +" ");
            cur = cur.next;
        }
        System.out.println();
    }
    
}

//链表结点的实体类
class Node{
    int data;//结点数据
    Node next;//下一个结点

    public Node(int data) {
        this.data = data;
    }    
    
}