單鏈表構(gòu)造方法

Java

JVM有棧區(qū)和堆區(qū)

棧區(qū)：存引用，就是指向?qū)嶋H對(duì)象的地址。。

堆區(qū)：存的是創(chuàng)建的對(duì)象。

定義

規(guī)范的鏈表定義

public class ListNode{
    private int data;
    private ListNode next;
    public ListNode(int data){
        this.data=data;
    }
    public int getData(){
        return data;
    }
    public void setData(int data){
        this.data=data;
    }
    public ListNode getNext(){
        return next;
    }
    public void setNext(ListNode next){
        this.next=next;
    }
}

LeetCode算法題中常用

public class ListNode {
    public int val;
    public Node next;
    Node(int x) {
        val = x;
        ext = null;//作用不大，寫(xiě)了更標(biāo)準(zhǔn)
    }
}

遍歷

public static int getListLength(Node head){
    int length=0;
    Node node=head;
    while(node!=null){
        length++;
        node=node.next;
    }
    return length;
}

插入

public static Node insertNode(Node head,Node nodeInsert,int position){
    //將節(jié)點(diǎn)插入一個(gè)空鏈表
    if(head==null){
        return nodeInsert;
    }
    //越界
    int size=getLength(head);
    if(position>size+1||position<1){
        System.out.println("位置參數(shù)越界");
        return head;
    }
    //表頭插入
    if(position)==1){
        nodeInsert.next=head;
        head=nodeeInsert;
        return head;
    }
    //其他位置插入
    Node pNode=head;
    int count=1;
    while(count<position-1){
        pNode=pNode.next;
        count++;
    }
    nodeInsert.next=pNode.next;
    pNode.next=nodeinsert;
    return head;    
}

刪除

public static Node deleteNode(Node head,int position){
    //排除空鏈表
    if(head==null){
        return null;
    }
    //越界
    int size=getLength(head);
    if(position >size+1||position <1){
        System.out.println("位置參數(shù)越界");
        return head;
    } 
    //刪除節(jié)點(diǎn)
    if(position==1){
        head=head.next;
    }else{
        Node pNode=head;
        int count =1;
        while(count<position-1){
            count++;
            pNode=pNode.next;
        }
        Node delNode=pNode.next;
        pNode.next=delNode.next;
    }
    return head;
}

雙向鏈表

Java

結(jié)點(diǎn)

class DoubleNode{
    public int data;
    public DoubleNode pre;
    public DoubleNode next;
    public DoubleNode(int data){
        this.data=data;
    }
}

結(jié)構(gòu)&遍歷

public class DoubleLinkList{
    private DoubleNode first;
    private DoubleNode last;
    public DoubleLinkList(){
        first=null;
        last=first;
    }
    //從頭遍歷
    public void displayForward(){
        DoubleNode current=first;
        while(current!=null){
            current.displayNode();
            current=current.next;
        }
    }
    //從尾部遍歷
    public void displayBackward(){
        DoubleNode current=last;
        while(current!=null){
            current.displayNode();
            current=current.pre;
        }
    }
}

插入

從頭插入

DoublyLinkList doublyLinkList = new DoublyLinkList();
doublyLinkList.insertFirst(20);
public void insertFirst(int data) {
    DoubleNode newDoubleNode = new DoubleNode(data);
    if (isEmpty()) {
        last=newDoubleNode;//列表初始化時(shí)first，last都為null
    }else{
        first.pre=newDoubleNode;
        newDoubleNode.next=first;
    }	
    first=newDoubleNode;//讓該結(jié)點(diǎn)稱(chēng)為第一個(gè)節(jié)點(diǎn)
}

從尾插入

public void insertLast(int data) {
    DoubleNode newDoubleNode = new DoubleNode(data);
    if (isEmpty()) {
        first=newDoubleNode;//列表初始化時(shí)first，last都為null
    }else{
        newDoubleNode.pre=last;
        last.next=newDoubleNode;
    }
    last=newDoubleNode;//讓該結(jié)點(diǎn)稱(chēng)為最后一個(gè)節(jié)點(diǎn)
}

從某個(gè)值為key的節(jié)點(diǎn)后面插入

public void insertAfter(int key, int data){
    DoubleNode newDoubleNode = new DoubleNode(data);
    DoubleNode current = first;
    //找值為key的節(jié)點(diǎn)
    while ((current != null) && (current.data != key)){
        current = current.next;
    }
    //若current==null，要么鏈表為空，要么沒(méi)有值為key的數(shù)
    if (current == null){
       //根據(jù)題意來(lái)寫(xiě)... 
    }else{
        //這里還有可能key值是最后一個(gè)數(shù)，寫(xiě)法參考上面，這里不再考慮
        newDoubleNode.next=current.next;
        current.next.prev = newDoubleNode;
        newDoubleNode.pre=current;
        current.next=newDoubleNode;
    }
}

刪除

刪除頭結(jié)點(diǎn)

public DoubleNode deleteFirst(){
    //如果只有一個(gè)節(jié)點(diǎn)。需要多考慮一個(gè)變量last
    if (first.next == null){
        last=null;
    }else{
        first.next.pre=null;
    }
    first=first.next;  
}

刪除尾結(jié)點(diǎn)

public DoubleNode deleteLast(){
    //如果只有一個(gè)節(jié)點(diǎn)。需要多考慮一個(gè)變量first
    if (first.next == null){
        first=null;
    }else{
        last.pre.next=null;
    }
    last=last.pre;
}

按值刪除文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-608647.html

public DoubleNode deleteKey(int key){
    DoubleNode current = first;
    //尋找key值所在的節(jié)點(diǎn)
    while (current != null && current.data != key){
        current = current.next;
    }
    //若current==null，要么鏈表為空，要么沒(méi)有值為key的數(shù)
    if (current == null){
       //根據(jù)題意來(lái)寫(xiě)...
        return null;
    }else{
        //這里還有可能key值是第一個(gè)或者最后一個(gè)數(shù)，寫(xiě)法參考上面，這里不再考慮 
        current.next.prev = current.pre;
        current.pre.next=current.next;
    }
}

到了這里，關(guān)于編程導(dǎo)航算法通關(guān)村第一關(guān)|青銅|鏈表基礎(chǔ)的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！