鏈表

單鏈表

C實(shí)現(xiàn)
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

typedef struct NODE{
    int data;
    NODE *next;
}Node;

// 刪除節(jié)點(diǎn)
void deleteNode(Node *pHead, int index){
    int count = 0;
    while (pHead->next != NULL && count < index)
    {
        pHead = pHead->next;
        count++;
    }

    Node *delNode = pHead->next;
    pHead->next = delNode->next;
    free(delNode);
}

// 更新節(jié)點(diǎn)
void updateNode(Node *pHead,Node *node,int index){
    int count = 0;
    while (pHead->next != NULL && count < index)
    {
        pHead = pHead->next;
        count++;
    }

    Node *delNode = pHead->next;
    pHead->next = delNode->next;
    free(delNode);

    node->next = pHead->next;
    pHead->next = node;
}

// 增加節(jié)點(diǎn)
void addNode(Node *pHead,Node *node,int index){
    int count = 0;
    while (pHead->next != NULL && count < index)
    {
        pHead = pHead->next;
        count++;
    }
    node->next = pHead->next;
    pHead->next = node;
}

// 創(chuàng)建鏈表(頭插法)
void createList1(Node *pHead){
    Node *p;
    Node *next = (Node *)malloc(sizeof(Node));
    next->data = 45;
    next->next = NULL;
    int i;
    for (i = 0; i < 10; i ++){
        p = (Node *)malloc(sizeof(Node));
        p->data = i;
        if (i == 0)
        {
            p->next = NULL;
        }
        else{
            p->next = next;
        }
    
        pHead->next = p;
        next = p;
    }
}

// 創(chuàng)建鏈表（尾插法）
void createList(Node *pHead){
    printf("createList     %p\n", pHead);
    Node *p;
    int i;
    for (i = 0; i < 10;i++){
        p = (Node *)malloc(sizeof(Node));
        if (p == NULL)
        {
            printf("申請(qǐng)失敗\n");
            break;
        }

        p->data = i;
        p->next = NULL;
        //printf("%d\t%p\n",p->data,*p);
        pHead->next = p;
        pHead = p;
    }
}

// 遍歷鏈表
void printList(Node *pHead){
    if (pHead == NULL){
        printf("鏈表為空\(chéng)n");
    }
    while (pHead != NULL){
        printf("%d\n",pHead->data);
        pHead = pHead->next;
    }

    printf("鏈表遍歷完畢\n");
}

//反轉(zhuǎn)鏈表
void reversalList(Node *pHead){
    Node *pre = pHead->next;
    Node *last = pre->next;
    Node *temp = last->next;
    pre->next = NULL;

    while (temp != NULL)
    {
        last->next = pre;
        pre = last;
        last = temp;
        temp = temp->next;
    }
    last->next = pre;
    pHead->next = last;
}
Java實(shí)現(xiàn)
    /**
     * 創(chuàng)建列表
     * @return
     */
    private static Node createList(Node head){
        Node temp = new Node();
        for (int i = 0; i < 2; i++) {
            Node node = new Node();
            node.data = (i+1) + "";
            node.next = null;
            if(i == 0){
                head.next = node;
            }
            temp.next = node;
            temp = node;
        }
        return head;
    }
    
    /**
     * 遍歷列表
     * @param head
     */
    private static void printList(Node head){
        if(head == null || head.next == null){
            return ;
        }
        
        while(head.data != null){
            System.out.print(head.data+"\t");
            if(head.next == null){
                break;
            }
            head = head.next;
        }
    }
    
    /**
     * 在鏈表中添加節(jié)點(diǎn)
     * @param node  要添加的節(jié)點(diǎn)
     * @param index  要添加的位置
     * @param head   被添加的鏈表
     */
    private static void addNode(Node node,int index,Node head){
        if(index < 0 || index > getLength(head)){
            System.out.println("插入的位置不對(duì)，請(qǐng)重試");
            return;
        }
        
        int count = 0;
        while(count < index){
            head = head.next;
            count ++;
        }
        
        node.next = head.next;
        head.next = node;
    }
    
    /**
     * 刪除節(jié)點(diǎn)
     * @param index  要?jiǎng)h除節(jié)點(diǎn)的位置
     * @param head    被刪的鏈表
     */
    private static void deleteNode(int index,Node head){
        if(index < 0 || index > getLength(head)){
            System.out.println("要?jiǎng)h除的位置不對(duì)，請(qǐng)重試");
            return;
        }
        
        int count = 0;
        while(count < index){
            head = head.next;
            count++;
        }
        
        head.next = head.next.next;
    }
    
    /**
     * 更新鏈表某處的節(jié)點(diǎn)
     * @param node   需要更新的新節(jié)點(diǎn)
     * @param index  需要更新的位置
     * @param head   被更新的鏈表
     */
    private static void updateNode (Node node,int index,Node head){
        if(index < 0 || index > getLength(head)){
            System.out.println("要更新的位置不對(duì)，請(qǐng)重試");
            return;
        }
        
        int count = 0;
        while(count < index){
            head = head.next;
            count ++;
        }
        
        head.next = head.next.next;
        node.next = head.next;
        head.next = node;
    }
    /**
     * 獲取鏈表長(zhǎng)度
     * @param head
     * @return
     */
    private static int getLength(Node head){
        Node list = head.next;
        int length = 0;
        while(list.next != null){
            length ++;
            list = list.next;
        }
        return (length+1);
    }
    
    /**
     * 反轉(zhuǎn)鏈表
     * @param node
     */
    private static Node reversalList(Node head){
        Node mid = head.next;
        Node next = mid.next;
        Node temp = next.next;
        mid.next = null;
        
        while(temp != null){
            next.next = mid;
            mid = next;
            next = temp;
            temp = temp.next;
        }
        
        next.next = mid;
        head = next;
        return head;
    }
    
    static class Node{
        public String data;
        public Node next;
    }

雙鏈表

C實(shí)現(xiàn)
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>

typedef struct NODE{
    int data;
    NODE *previous;
    NODE *next;
}Node;

// 創(chuàng)建鏈表
void crateList(Node *head,Node *tail){
    
    Node * temp = head;
    for (int i = 0; i < 10; i++){
        Node *node = (Node *)malloc(sizeof(Node));
        node->data = i;
        node->previous = temp;
        node->next = NULL;

        temp->next = node;
        temp = node;
    }

    temp->next = tail;
    tail->previous = temp;
}


// 遍歷鏈表
void printList(Node *head,Node * tail){
    if (head == NULL){
        printf("鏈表為空");
        return;
    }
    Node *node = head->next;
    while (node->data != -2){
        printf("%d\n", node->data);
        node = node->next;
    }
}

// 獲取長(zhǎng)度
int getLength(Node *head){
    if (head == NULL){
        printf("鏈表為空");
        return 0;
    }
    int count = 0;
    Node *temp = head->next;
    while (temp->data != -2){
        temp = temp->next;
        count++;
    }
    return count;
}

// 增加節(jié)點(diǎn)
void addNode(Node *node,int index,Node *head,Node *tail){
    if (index < 0 || index > getLength(head))
    {
        printf("插入位置不對(duì)");
        return;
    }

    int count = 0;
    while (count < index){
        count++;
        head = head->next;
    }

    node->previous = head;
    node->next = head->next;
    head->next->previous = node;
    head->next = node;
}

// 刪除節(jié)點(diǎn)
void deleteNode(int index, Node *head, Node *tail){
    if (index < 0 || index > getLength(head))
    {
        printf("刪除位置不對(duì)");
        return;
    }

    int count = 1;
    while (count < index){
        count++;
        head = head->next;
    }

    Node *temp = head->next;
    head->next = temp->next;
    temp->next->previous = head;
    temp->previous = NULL;
    temp->next = NULL;
    free(temp);
}
Java實(shí)現(xiàn)
    /**
     * 創(chuàng)建鏈表 
     * @param head 鏈表的頭結(jié)點(diǎn)
     * @param tail 鏈表的尾結(jié)點(diǎn)
     */
    private static void createList(Node head,Node tail){
        Node front = head;
        
        for (int i = 0; i < 10; i++) {
            Node node = new Node();
            node.data = (i + 1) + "";
            node.previous = front;
            node.next = null;
            
            front.next = node;
            front = node;
        }
        
        front.next = tail;
        tail.previous = front;
    }
    
    /**
     * 遍歷鏈表
     * @param head
     */
    private static void printList(Node head){
        if(head == null || head.next == null){
            System.out.println("鏈表為空");
            return;
        }
        System.out.println(head.data);
        while(head.next != null){
            head = head.next;
            System.out.println(head.data);
        }
    }
    
    /**
     * 獲取鏈表長(zhǎng)度
     * @param head
     * @return
     */
    private static int getLength(Node head){
        if(head == null || head.next == null){
            return 0;
        }

        int length = 0;
        while(head.next != null){
            head = head.next;
            length++;
        }
        return length - 1;
    }
    
    /**
     * 添加節(jié)點(diǎn)
     * @param node   需添加的節(jié)點(diǎn)
     * @param index   添加的位置
     * @param head   被添加鏈表的頭結(jié)點(diǎn)
     * @param tail   被添加鏈表的尾節(jié)點(diǎn)
     */
    private static void addNode(Node node,int index,Node head,Node tail){
        if(index < 0 || index > getLength(head)){
            System.out.println("插入的位置不對(duì)");
            return;
        }
        if(index > getLength(head) / 2){
            // 從尾部插入
            int length = getLength(head);
            while(length > index){
                length --;
                tail = tail.previous;
            }
            
            node.next = tail;
            node.previous = tail.previous;
            tail.previous.next = node;
            tail.previous = node;
        }else{
            // 從頭插入
            int count = 0;
            while(count < index){
                count++;
                head = head.next;
            }
            
            node.previous = head;
            node.next = head.next;
            head.next.previous = node;
            head.next = node;
        }
    }
    
    /**
     * 刪除節(jié)點(diǎn)
     * @param index  要?jiǎng)h除的位置
     * @param head
     * @param tail
     */
    private static void deleteNode(int index,Node head,Node tail){
        if(index <= 0 || index > getLength(head)){
            System.out.println("插入的位置不對(duì)");
            return;
        }
        
        if(index > getLength(head) / 2){
            int length = getLength(head);
            while(length > index){
                length -- ;
                tail = tail.previous;
            }
            
            Node temp = tail.previous;
            temp.previous.next = tail;
            tail.previous = temp.previous;
            temp.previous = null;
            temp.next = null;
        }else{
            int count = 0;
            while(count < index - 1){
                count++;
                head = head.next;
            }
            
            Node temp = head.next;
            temp.next.previous = head;
            head.next = temp.next;
            temp.previous = null;
            temp.next = null;
        }
    }

    static class Node{
        public String data;
        public Node previous;
        public Node next;
    }
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 最近在復(fù)習(xí)數(shù)據(jù)結(jié)構(gòu)時(shí)，感觸頗深。 推薦程序員們有時(shí)間都可以復(fù)習(xí)下， 數(shù)據(jù)結(jié)構(gòu)不僅僅是一門(mén)課程， 它更能理清我們開(kāi)發(fā)...
    Bobby0322閱讀 3,261評(píng)論 0贊 4
  • 作為一個(gè)資深的新手程序員??,鏈表這些既基礎(chǔ)又深?yuàn)W的東西是日常工作中并不常見(jiàn),但是卻非常重要,所以就總結(jié)一下鏈表的簡(jiǎn)...
    Clark_new閱讀 4,494評(píng)論 4贊 12
  • //leetcode中還有花樣鏈表題，這里幾個(gè)例子，冰山一角 求單鏈表中結(jié)點(diǎn)的個(gè)數(shù)----時(shí)間復(fù)雜度O（n）這是最...
    暗黑破壞球嘿哈閱讀 1,656評(píng)論 0贊 6
  • 轉(zhuǎn)載請(qǐng)注明出處：http://www.itdecent.cn/p/c65d9d753c31 在上一篇博客《數(shù)據(jù)結(jié)構(gòu)...
    Alent閱讀 3,597評(píng)論 4贊 74
  • 你是這樣的女孩子嗎——或者曾經(jīng)是？ 從小都有著公主夢(mèng)，粉紅色的夢(mèng)里自己會(huì)是穿著漂亮的蓬蓬裙、戴著白手套，高貴地走路...
    婉玲閱讀 1,345評(píng)論 0贊 3

友情鏈接更多精彩內(nèi)容