数据结构(1)——链表结构（java实现单链表）

链表结构

• 数据部分：保存的是该结点的实际数据。
• 地址部分：保存的是下一个结点的地址。
  

java实现单链表

//数据元素封装类
class NodeData {
    public String key;
    public int age;
    public String name;
}

//链表的封装类
public class LinkList {

    NodeData nodeData = new NodeData();
    LinkList nextNode;

    //从尾部添加结点
    LinkList addEnd(LinkList head, NodeData nodeData) {

        LinkList node, htemp;

        if ((node = new LinkList()) == null) {
            System.out.println("申请内存失败！");
            return null;
        } else {
            //保存数据
            node.nodeData = nodeData;
            //设置结点引用为空，即为表尾
            node.nextNode = null;
            //头引用
            if (head == null) {
                head = node;
                return head;
            }
            htemp = head;
            //查找链表的末尾
            while (htemp.nextNode != null) {
                htemp = htemp.nextNode;
            }
            htemp.nextNode = node;
            return head;
        }

    }

    //从头部添加结点
    LinkList addStart(LinkList head, NodeData nodeData) {
        LinkList node;
        if ((node = new LinkList()) == null) {
            System.out.println("申请内存失败！");
            return null;
        } else {
            //保存数据
            node.nodeData = nodeData;
            //指向头引用所指结点
            node.nextNode = head;
            //头引用指向新增结点
            head = node;
            return head;
        }

    }

    //查找节点
    LinkList findNode(LinkList head, String key) {
        //保存链表头引用
        LinkList htemp;
        htemp = head;
        //若结点有效则进行查找
        while (htemp != null) {
            //若结点关键字与传入关键字相同
            if (htemp.nodeData.key.compareTo(key) == 0) {
                //返回结点引用
                return htemp;
            } else {
                //处理下一结点
                htemp = htemp.nextNode;
            }
        }
        return null;
    }

    //插入节点
    LinkList insertNode(LinkList head, String findKey, NodeData nodeData) {
        LinkList node, nodeTemp;
        if ((node = new LinkList()) == null) {
            System.out.println("申请内存失败！");
            return null;
        }
        node.nodeData = nodeData;
        nodeTemp = findNode(head, findKey);
        if (nodeTemp != null) {
            node.nextNode = nodeTemp.nextNode;
            nodeTemp.nextNode = node;
        } else {
            System.out.println("未找到正确插入位置");
            //free(node);
        }
        return head;
    }

    //删除结点
    int deleteNode(LinkList head, String key) {
        LinkList node, htemp;
        htemp = head;
        node = head;
        while (htemp != null) {
            if (htemp.nodeData.key.compareTo(key) == 0) {
                //使前一结点指向当前结点的下一结点
                node.nextNode = htemp.nextNode;
                //free(node);
                return 1;
            } else {
                node = htemp;
                htemp = htemp.nextNode;
            }
        }
        return 0;
    }

    //获取链表长度
    int getLength(LinkList head) {
        LinkList htemp;
        int len = 0;
        htemp = head;
        while (htemp != null) {
            len++;
            htemp = htemp.nextNode;
        }
        return len;
    }

    void displayList(LinkList head) {
        LinkList htemp;
        NodeData nodeData;
        htemp = head;
        System.out.println("当前链表共有" + getLength(head) + "个结点。链表所有结点如下：");
        while (htemp != null) {
            nodeData = htemp.nodeData;
            System.out.println(nodeData.key + " " + nodeData.name+ " " + nodeData.age);
            htemp = htemp.nextNode;
        }
    }
    //测试
    public static void main(String[] args) {
        LinkList node, head = null;
        LinkList linkList = new LinkList();
        String key, findKey;
        Scanner input = new Scanner(System.in);
        System.out.println("链表test。请为链表输入数据，格式为: 关键字  姓名  年龄");
        do {
            NodeData nodeData = new NodeData();
            nodeData.key = input.next();
            if (nodeData.key.equals("0")) {
                break;
            } else {
                nodeData.name = input.next();
                nodeData.age = input.nextInt();
                head = linkList.addEnd(head, nodeData);
            }
        } while (true);
        linkList.displayList(head);

        System.out.println("演示插入结点，输入插入位置的关键字：");
        findKey = input.next();
        System.out.println("输入插入结点的数据（关键字 姓名 年龄）：");
        NodeData nodeData = new NodeData();
        nodeData.key = input.next();
        nodeData.name = input.next();
        nodeData.age = input.nextInt();
        head = linkList.insertNode(head, findKey, nodeData);
        linkList.displayList(head);

        System.out.println("演示删除结点，请输入要删除的关键字");
        key = input.next();
        linkList.deleteNode(head,key);
        linkList.displayList(head);
        System.out.println("演示在链表中查找，输入查找关键字：");
        key = input.next();
        node = linkList.findNode(head,key);
        if (node!=null){
            nodeData = node.nodeData;
            System.out.println(nodeData.key + " " + nodeData.name + " " + nodeData.age);
        }else{
            System.out.println("在表中为找到关键字为"+key+"的结点");
        }
    }

}