美文网首页
链表

链表

作者: youtianlong123 | 来源:发表于2017-11-07 15:36 被阅读0次

单链表

C实现
#include "stdafx.h"
#include <stdio.h>
#include <stdlib.h>

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

// 删除节点
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);
}

// 更新节点
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;
}

// 增加节点
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;
}

// 创建链表(头插法)
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;
    }
}

// 创建链表（尾插法）
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("申请失败\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("链表为空\n");
    }
    while (pHead != NULL){
        printf("%d\n",pHead->data);
        pHead = pHead->next;
    }

    printf("链表遍历完毕\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实现
    /**
     * 创建列表
     * @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;
        }
    }
    
    /**
     * 在链表中添加节点
     * @param node  要添加的节点
     * @param index  要添加的位置
     * @param head   被添加的链表
     */
    private static void addNode(Node node,int index,Node head){
        if(index < 0 || index > getLength(head)){
            System.out.println("插入的位置不对，请重试");
            return;
        }
        
        int count = 0;
        while(count < index){
            head = head.next;
            count ++;
        }
        
        node.next = head.next;
        head.next = node;
    }
    
    /**
     * 删除节点
     * @param index  要删除节点的位置
     * @param head    被删的链表
     */
    private static void deleteNode(int index,Node head){
        if(index < 0 || index > getLength(head)){
            System.out.println("要删除的位置不对，请重试");
            return;
        }
        
        int count = 0;
        while(count < index){
            head = head.next;
            count++;
        }
        
        head.next = head.next.next;
    }
    
    /**
     * 更新链表某处的节点
     * @param node   需要更新的新节点
     * @param index  需要更新的位置
     * @param head   被更新的链表
     */
    private static void updateNode (Node node,int index,Node head){
        if(index < 0 || index > getLength(head)){
            System.out.println("要更新的位置不对，请重试");
            return;
        }
        
        int count = 0;
        while(count < index){
            head = head.next;
            count ++;
        }
        
        head.next = head.next.next;
        node.next = head.next;
        head.next = node;
    }
    /**
     * 获取链表长度
     * @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);
    }
    
    /**
     * 反转链表
     * @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实现
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>

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

// 创建链表
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;
    }
}

// 获取长度
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;
}

// 增加节点
void addNode(Node *node,int index,Node *head,Node *tail){
    if (index < 0 || index > getLength(head))
    {
        printf("插入位置不对");
        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;
}

// 删除节点
void deleteNode(int index, Node *head, Node *tail){
    if (index < 0 || index > getLength(head))
    {
        printf("删除位置不对");
        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实现
    /**
     * 创建链表 
     * @param head 链表的头结点
     * @param tail 链表的尾结点
     */
    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);
        }
    }
    
    /**
     * 获取链表长度
     * @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;
    }
    
    /**
     * 添加节点
     * @param node   需添加的节点
     * @param index   添加的位置
     * @param head   被添加链表的头结点
     * @param tail   被添加链表的尾节点
     */
    private static void addNode(Node node,int index,Node head,Node tail){
        if(index < 0 || index > getLength(head)){
            System.out.println("插入的位置不对");
            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;
        }
    }
    
    /**
     * 删除节点
     * @param index  要删除的位置
     * @param head
     * @param tail
     */
    private static void deleteNode(int index,Node head,Node tail){
        if(index <= 0 || index > getLength(head)){
            System.out.println("插入的位置不对");
            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;
    }

相关文章

  • 链表基础

    链表基础 链表长度 链表为空 链表结构 链表增加

  • 双向链表&双向循环链表

    链表分为：单链表、单向循环链表、双向链表、双向循环链表本节主要说明：双向链表、双向循环链表 定义结点 一、双向链表...

  • 算法与数据结构:链表

    链表 链表还分为单向链表和双向链表, 但是这篇文章只说单向链表 , 下次再讲双向链表 . 链表和数组的区别 ? 链...

  • 链表

    链表 单链表反转链表中环的检测两个有序链表合并删除链表倒数第n个节点求链表的元素总个数 一.单向链表 链表共有特征...

  • 五、双向链表

    双向链表 此前介绍的链表，也叫做单向链表使用双向链表可以提升链表的综合性能 修改之前的单链表的源码： 双向链表 –...

  • 链表

    内容 链表数据结构 向链表添加元素 从链表移除元素 使用 LinkedList 表 双向链表 循环链表 链表数据结...

  • 数据与算法结构

    线性表 顺序表 链表（物理上离散，逻辑上连续） 链表的类别 单链表 循环链表 双链表 链表的操作 顺序表与链表的比...

  • 数据结构——链表

    本文所讲的链表是单链表，链表采用无头链表 科普下：一般链表可以分为有头节点的链表与无头节点的链表 有头节点的链表：...

  • 链表

    文章结构 链表的定义 链表的插入和删除操作 链表的特性 常见的链表结构 自定义链表 链表的经典操作 使用链表实现L...

  • Algorithm小白入门 -- 单链表

    单链表递归反转链表k个一组反转链表回文链表 1. 递归反转链表 单链表节点的结构如下： 1.1 递归反转整个单链表...

网友评论

      本文标题：链表

      本文链接：https://www.haomeiwen.com/subject/vjakmxtx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|链表|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！