数据结构(四)-单链表

Game.of.Thrones

单向链表是一种线性表，由一系列的节点（Node）组成。每个结点包括两个部分：存储数据元素的数据域和存储下一个结点地址的指针域。由于链表不按顺序存储，在插入的时候可以达到O(1)的复杂度，比顺序表快得多，但是查找一个节点时则需要O(n)的时间，而顺序表的时间复杂度是O(1)。

package com.lq.linklist;
/**
 * 链表结构，链结点
 */
public class Node {
    //这里为了方便，将变量的属性设置为public
    public long data;//数据域 
    public Node next;//结点域(指针域)

    public Node(long value){
        this.data = value;
    }

    public void display(){
        System.out.print(data+" ");
    }
}

package com.lq.linklist;

public class LinkList {
    
    private Node head;//头结点

    public LinkList(){
        head = null;
    }
    /**
     * 插入一个结点，在头结点后进行插入
     */
    public void insertFirst(long value){
        Node node = new Node(value);
        node.next = head;
        head = node;
    }
    /**
     * 在链表的指定位置插入结点。
     * index:插入链表的位置，从1开始
     * node:插入的结点
     */
    public void insertNodeById(int id,Node node){
        //首先需要判断指定位置是否合法，
        if(id<1||id>length()+1){
            System.out.println("插入位置不合法。");
            return;
        }
        int length = 1;           
        Node temp = head;       
        while(head.next != null){
            if(id == length++){                  
                node.next = temp.next;//temp代表的是当前位置的前一个结点。            
                temp.next = node;                
                return;
            }
            temp = temp.next;
        }
    }
    /**
     * 删除一个结点，在头结点后进行删除
     */
    public Node deleteFirst(){
        Node temp = head;
        head = temp.next;
        return temp;
    }
    /**
     * 通过id删除指定位置的结点 
     */
    public void delNodeById(int id){
        //判断index是否合理
        if(id<1 || id>length()){
            System.out.println("给定的位置不合理");
            return;
        }
        int length=1;
        Node temp = head;
        while(temp.next != null){
            if(id == length++){             
                temp.next = temp.next.next;    
                return;
            }
            temp = temp.next;
        }    
    }
    /**
     * 显示方法
     */
    public void display(){
        Node current = head;
        while (current != null){
            current.display();   //打印结点
            current = current.next;
        }
    }
    /**
     * 查找方法
     */
    public Node find(long value){
        Node current = head;
        while (current.data != value){
            if (current.next == null){
                System.out.println("没有这个数");
                return null;
            }
            current = current.next;
           
        }
        return current;
    }
    /**
     * 删除方法,根据数据域来进行删除
     */
    public Node delete(long value){
        Node current = head;
        Node previous = head;//表示前一个结点
        while (current.data != value){
            if (current.next == null){
                return null;
            }
            previous = current; 
            current = current.next; 
        }
        if (current == head){
            head = head.next;
        }else {
            previous.next = current.next;
        }
        return current;
    }

    /**
     * 计算单链表的长度，返回结点个数
     */
    public int length() {
        int length=0;
        Node temp = head;
        if(head==null){
            return length;
        }
        while(temp.next != null){
            length++;
            temp = temp.next;
        }
        return length+1;
    }
    /**
     * 对链表中的结点进行选择排序。
     */
    public void selectSortNode(){
        //判断链表长度大于2，不然只有一个元素，就不用排序了。
        if(length()<2){
            System.out.println("无需排序");
            return;
        }
        Node temp = head;            //第一层遍历使用的移动指针，最初指向头结点
        while(temp.next != null){    //第一层遍历链表，从第一个结点开始遍历
            Node secondTemp = temp.next;        
            while(secondTemp.next != null){//第二层遍历,从第二个结点开始遍历
                if( temp.next.data > secondTemp.next.data){
                    long t = secondTemp.next.data;
                    secondTemp.next.data =  temp.next.data;
                    temp.next.data = t;                
                }
                secondTemp = secondTemp.next;
            }
            temp = temp.next;
        }        
    }
}

测试

package com.lq.linklist;

public class TestLinkList {
    public static void main(String[] args) {
        LinkList linkList = new LinkList();
        linkList.insertFirst(10);
        linkList.insertFirst(20);
        linkList.insertFirst(30);
        linkList.display();      
       
        Node node = linkList.find(10);
        node.display();    
       
        Node node1 =new Node(25);
        linkList.insertNodeById(1, node1);
        linkList.display();
    }
}