精华内容
下载资源
问答
  • 单链表与双向链表

    2017-12-08 18:41:11
    单链表 链表中的数据是以节点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个...双向链表也叫双链表,是链表的一种,它的每个数据结
        单链表
    

    链表中的数据是以节点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。

    以"结点的序列"表示线性表称作线性链表(单链表)

    单链表是链式存取的结构,为找第 i 个数据元素,必须先找到第 i-1 个数据元素。

    双向链表

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表

    关于单链表的代码

    #include<stdio.h>
    #include<stdlib.h>
    #define len sizeof(struct number)
    struct number{
    	int value;
    	struct number *left;                       
    	struct number *right;
    };          
    struct number * create(int n){
    	struct number *head;
    	struct number *p1,*p2;
    	p1=p2=(struct number*)malloc(len);//关于该函数的原型,在以前malloc返回的是char型指针,新的ANSIC标准规定,该函数返回为void型指针
    	if(p1->left==NULL){
    		head=p1;
    		scanf("%d%d",&p1->value,&p2->value);
    		p1->right=p2;
    	}
    	else{
    		p1=(struct number*)malloc(len);
    		scanf("%d",p2->value);
    		p1->right=p2;
    		p2->right=NULL;
    	}
    	return(head);
    }
    int main(){  
    	struct number *pt;
    	printf("单链表:");
    	pt=create();
    	system("pause");
    }



    展开全文
  • 单链表与双链表

    2019-07-08 22:41:18
    单链表 结构: head|next->node1|next->…->noden|next->null 首先创建单链表要先声明好节点的数据参数和指向下一个数据节点的参数, 然后初始化头节点。 单链表在末尾添加数据时需要从头节点开始遍历...

    单链表

    • 结构:
      head|next->node1|next->…->noden|next->null
    • 首先创建单链表要先声明好节点的数据参数和指向下一个数据节点的参数,
      然后初始化头节点。
    • 单链表在末尾添加数据时需要从头节点开始遍历知道节点指向null,然后将最后一个节点指向要添加的数据然后让要添加的数据的next节点指向null
      head|next->node1|next->…->noden|next->        null;
                           ->new|next->
    • 删除操作需要遍历到要删除的节点的前一个节点然后让这个节点指向下下个节点的数据即可
      head|next->node1|next-  node2|next->   node3|next->…->noden|next->null;
                   ^ – - ->   ^
    • 插入操作需要遍历到要插入的节点的位置然后让要插入的数据指向下一个节点,然后让要前面的节点指向要插入的节点。
      head|next->node1|next- node2|next->           node3|next->…->noden|next->null;
                            ->new|next->
    • 替换操作是删除和插入的结合

    双向链表

    • 结构:
      null<-previous|head|next->previous|node|next->. . . . . . . ->previous|noden|next->null
              ^< - - -  -|            ^<-- - --|
    • 与单链表相同都要先定义头结点,但它比单链表要多定义一个previous前驱指向前一个数据
    • 双向链表在添加替换删除时不仅需要将next指向后一个数据还需要要将前驱指向前一个数据。

    单链表的代码:

    包Link:
    • Node.java
    package Link;
    
    public class Node {
        int data;
        Node next;
    
    }
    
    • Link.java
    package Link;
    
    import java.sql.SQLOutput;
    
    public class Link {//初始化头结点
        private Node head;
        public void create(int data){
            Node node=new Node();
            node.data=data;
            node.next=null;
            head=node;
        }
        public int gethead(){
    
            return this.head.data;
        }
        public void add(int m){
            Node n=new Node();
            Node c;
            n.data=m;
            c=head;
            while (c.next!=null){
                c=c.next;
            }
            n.next=null;
            c.next=n;
        }
        public int getsize(){
            int size=0;
            Node m;
            m=head;
            while (m!=null){
                m=m.next;
                size++;
            }
            return size;
        }
        public void delete(int i){
            Node n;
            n=head;
            if(i<this.getsize()) {
                for (int j = 1; j < i - 1; j++) {
                    n = n.next;
                }
                n.next=n.next.next;
            }
            if(i==this.getsize()){
                n.next=null;
            }
            else {
                System.out.println("超出范围");
            }
        }
        public void list(){
            Node l;
            l=head;
            System.out.print("链表: ");
            for(int i=1;i<=this.getsize();i++){
                System.out.print(l.data+" ");
                l=l.next;
            }
            System.out.println();
        }
        public void insert(int i,int m){
            Node t=new Node();
            t.data=m;
            Node s;
            s=head;
            if(i<this.getsize()) {
                for (int j = 1; j < i; j++) {
                    s = s.next;
                }
                t.next = s.next;
                s.next = t;
            }
            if(i==this.getsize()){
                for (int j = 1; j < i; j++) {
                    s = s.next;
                }
                s.next=t;
                t.next=null;
            }
            else {
                System.out.println("超出范围");
            }
        }
        public void replace(int i,int r){
            Node t=new Node();
            t.data=r;
            Node s;
            s=head;
            if(i<this.getsize()) {
                for (int j = 1; j < i-1; j++) {
                    s=s.next;
                }
                t.next=s.next.next;
                s.next=t;
            }
            if(i==this.getsize()){
                for (int j = 1; j < i-1; j++) {
                    s=s.next;
                }
                s.next=null;
            }
            else {
                System.out.println("超出范围");
            }
        }
    }
    
    • Test.java
    package Link;
    
    import com.sun.org.apache.bcel.internal.generic.LNEG;
    
    public class Test {
        public static void main(String[] args) {
            Link link=new Link();
            link.create(1);
            int m=0;
            int n=link.gethead();
            System.out.println("头结点为:"+n);
            link.add(2);
            link.add(3);
            link.add(4);
            link.add(5);
            m=link.getsize();
            System.out.println("链表长度为:"+m);
            link.delete(3);
            System.out.println("删除第三个节点");
            link.list();
            m=link.getsize();
            System.out.println("链表长度为:"+m);
            link.add(6);
            link.add(7);
            link.delete(5);
            System.out.println("先在末尾添加6和7,然后删除第五个节点");
            link.list();
            link.insert(2,10);
            System.out.println("在第二个节点后插入10");
            link.list();
            link.replace(3,2);
            System.out.println("替换第三个节点为2");
            link.list();
        }
    }
    

    测试运行结果:
    头结点为:1
    链表长度为:5
    超出范围
    删除第三个节点
    链表: 1 2 4 5
    链表长度为:4
    先在末尾添加6和7,然后删除第五个节点
    链表: 1 2 4 5
    超出范围
    在第二个节点后插入10
    链表: 1 2 10 4 5
    超出范围
    替换第三个节点为2
    链表: 1 2 2 4 5

    双向链表的代码:

    包Link:
    • DoubleLink.java
    package DoubleLink;
    
    public class Node {
        Node next;
        Node previous;
        int data;
    }
    
    • Node.java
    package DoubleLink;
    
    public class DoubleLink {
        private Node head;
        public void create(int data,int data1){
            Node node=new Node();
            node.data=data;
            node.next=null;
            node.previous=null;
            head=node;
        }
        public int gethead(){
    
            return this.head.data;
        }
        public int getsize(){
            Node t;
            t=head;
            int size=0;
            while (t!=null){
                t=t.next;
                size++;
            }
            return size;
        }
        public void add(int a){
            Node t=new Node();
            Node s;
            t.data=a;
            s=head;
            while (s.next!=null){
                s=s.next;
            }
            t.next=null;
            t.previous=s;
            s.next=t;
    
        }
        public void list(){
            Node s;
            s=head;
            System.out.print("链表: ");
            for(int i=1;i<=this.getsize();i++){
                System.out.print(s.data+" ");
                s=s.next;
            }
            System.out.println();
        }
        public void insert(int i,int data){
            Node in=new Node();
            Node s;
            in.data=data;
            s=head;
            if(i<=this.getsize()) {
                for (int j = 1; j <i; j++) {
                   s=s.next;
                }
                in.next=s.next;
                s.next.previous=in;
                s.next=in;
                in.previous=s;
            }else {
                System.out.println("超出范围");
            }
        }
        public void delete(int i){
            Node n;
            n=head;
            if(i<this.getsize()) {
                for (int j = 1; j < i - 1; j++) {
                    n = n.next;
                }
                n.next=n.next.next;
                n.next.next.previous=n;
            }else {
                System.out.println("超出范围");
            }
        }
        public void replace(int i,int r){
            Node t=new Node();
            t.data=r;
            Node s;
            s=head;
            if(i<=this.getsize()) {
                for (int j = 1; j < i-1; j++) {
                    s=s.next;
                }
                t.next=s.next.next;
                t.previous=s;
                s.next=t;
            }else {
                System.out.println("超出范围");
            }
        }
    }
    
    • test0.java
    package DoubleLink;
    
    public class DoubleLink {
        private Node head;
        public void create(int data,int data1){
            Node node=new Node();
            node.data=data;
            node.next=null;
            node.previous=null;
            head=node;
        }
        public int gethead(){
    
            return this.head.data;
        }
        public int getsize(){
            Node t;
            t=head;
            int size=0;
            while (t!=null){
                t=t.next;
                size++;
            }
            return size;
        }
        public void add(int a){
            Node t=new Node();
            Node s;
            t.data=a;
            s=head;
            while (s.next!=null){
                s=s.next;
            }
            t.next=null;
            t.previous=s;
            s.next=t;
    
        }
        public void list(){
            Node s;
            s=head;
            System.out.print("链表: ");
            for(int i=1;i<=this.getsize();i++){
                System.out.print(s.data+" ");
                s=s.next;
            }
            System.out.println();
        }
        public void insert(int i,int data){
            Node in=new Node();
            Node s;
            in.data=data;
            s=head;
            if(i<=this.getsize()) {
                for (int j = 1; j <i; j++) {
                   s=s.next;
                }
                in.next=s.next;
                s.next.previous=in;
                s.next=in;
                in.previous=s;
            }else {
                System.out.println("超出范围");
            }
        }
        public void delete(int i){
            Node n;
            n=head;
            if(i<this.getsize()) {
                for (int j = 1; j < i - 1; j++) {
                    n = n.next;
                }
                n.next=n.next.next;
                n.next.next.previous=n;
            }else {
                System.out.println("超出范围");
            }
        }
        public void replace(int i,int r){
            Node t=new Node();
            t.data=r;
            Node s;
            s=head;
            if(i<=this.getsize()) {
                for (int j = 1; j < i-1; j++) {
                    s=s.next;
                }
                t.next=s.next.next;
                t.previous=s;
                s.next=t;
            }else {
                System.out.println("超出范围");
            }
        }
    }
    

    运行结果:
    头结点为:1
    链表的size:4
    链表: 1 3 4 5
    在第三个位置添加7
    链表: 1 3 4 7 5
    删除第三个位置
    链表: 1 3 7 5
    替换第二个位置为8
    链表: 1 8 7 5

    展开全文
  • Node环境下通过npm可以获取list的几个相关库,但是我们这里注重于自己动手实现,接下来就一起来看一下Node.js环境下JavaScript实现单链表与双链表结构
  • c++实现单链表与双链表的基本操作,包含建立,插入,删除,遍历等。
  • 参考文章 浅谈单链表与双链表的区别 案例 LeetCode进阶-实战之LRU缓存机制(阿里面试题)
    展开全文
  • 单链表与双链表知识点:1.单链表和双链表的定义需要注意的地方:检测耗费的时间:单链表和双链表的关系手写c++中的LinkedList 具体代码请看:NDKPractice项目的datastructure 知识点: 1.单链表和双链表的定义 ...

    具体代码请看:NDKPractice项目的datastructure

    1.单链表和双链表的定义

    • 单链表:只有一个指向下一结点的指针,也就是只能next
    • 双链表:除了有一个指向下一结点的指针外,还有一个指向前一结点的指针,可以通过prev()快速找到前一结点,顾名思义,单链表只能单向读取

    2.需要注意的地方:

    结构体或class 属性必须指定或者定义的时候给个默认对象这样才会有默认值,否则没有

    3.检测耗费的时间:

    time_t start = clock();
    ... // 这块是需要检测耗费时间的步骤
    time_t end = clock();
    LOGE("耗费时间:%d",(end-start) / CLOCKS_PER_SEC);
    

    4.单链表和双链表的关系

    1. 都是属于增删快的
    2. 双链表比单链表数据量大时查询要快一倍.(插入在链表中间时,可以根据需要从first,还是last查询,这样要快一倍)

    5.手写c++中的LinkedList

    //
    // Created by 123 on 2020/7/1.
    //
    
    #ifndef NDKPRACTICE_LINKEDLIST_HPP
    #define NDKPRACTICE_LINKEDLIST_HPP
    
    #include <assert.h>
    #include <android/log.h>
    
    // 单链表节点
    template<class E>
    struct Node {
        Node<E> *pre;
        Node<E> *next;
        E value;
    public:
        Node(E value, Node<E> *pre, Node<E> *next) : value(value), pre(pre), next(next) {}
    };
    
    // list
    template<class E>
    class LinkedList {
    private:
        // 头节点
        Node<E> *first = NULL;
        // 集合的长度
        int len = 0;
        // 尾节点
        Node<E> *last = NULL;
    public:
        void push(E e);
    
        int size();
    
        E get(int index);
    
        // remove insert
        void insert(int index, E e);
    
        E remove(int index);
    
        ~LinkedList();
    
    private:
        Node<E> *node(int index);
    
        void linkLast(E e);
    
        void linkBefore(Node<E> *pNode, E e);
    
        E unlink(Node<E> *pNode);
    };
    
    template<class E>
    void LinkedList<E>::push(E e) {
        // 添加一个数据在列表的后面
        linkLast(e);
    
    
        // 下面是单链表的添加
        /*Node<E> *new_node = new Node<E>(e, NULL);
    
        if (head) {// 0 -> 1 -> 2 -> 3
            // ?
            // head->next = new_node;
            // 找到尾巴节点,有一个特定就是 next 节点为空
            *//*Node<E>* h = head;
            while(h){
                if(h->next == NULL){
                    break;
                }
                h = h->next;
            }
            h->next = new_node;*//*
            // 每一次都需要找到最后一个节点  50000
            // 记录 last 节点
    
            // Node<E> *last = node(len - 1);
            last->next = new_node;// O(1)
        } else {
            head = new_node;
        }
        last = new_node;*/
    }
    
    template<class E>
    int LinkedList<E>::size() {
        return len;
    }
    
    template<class E>
    Node<E>* LinkedList<E>::node(int index) { // O(n)
        if(index < (len >> 1)){ // 从开头开始找要快点
            Node<E> *x = first;
            for(int i = 0; i< index; i++){
                x = x->next;
            }
            return x;
        }else{
            // 从后往前遍历
            Node<E> *x = last;
            for(int i = len-1; i > index; i--){
                x = x->pre;
            }
            return x;
        }
    }
    
    
    template<class E>
    E LinkedList<E>::get(int index) {
        assert(index>=0 && index < len);
        return node(index)->value;
    }
    
    template<class E>
    void LinkedList<E>::insert(int index, E e) { // len = 4;
        assert(index>=0 && index <= len);
        // 考虑边界 0
        if(index == len){
            linkLast(e);
        }else{
            linkBefore(node(index),e);
        }
    
    
        // 下面是单链表的插入
        /*Node<E> *new_node = new Node<E>(e, NULL);
        if (index == 0) {
            Node<E> *h = head;
            head = new_node;
            new_node->next = h;
        } else {
            // 考虑最后一个位置
            Node<E> *prev = node(index - 1);
            Node<E> *next = prev->next;// NULL
            prev->next = new_node;
            new_node->next = next;
        }*/
    }
    
    template<class E>
    E LinkedList<E>::remove(int index) {
        // 考虑边界问题 0 , len ,mid
        assert(index>=0 && index < len);
        return unlink(node(index));
    
        // 单链表的移除
        /*if (index == 0) {
        Node<E> *h = head;
        head = h->next;
        // 释放
        delete h;
        } else {
            Node<E> *prev = node(index - 1);
            // 删除的节点
            Node<E> *cur = prev->next;
            prev->next = cur->next;
            delete cur;
        }*/
    }
    
    template<class E>
    LinkedList<E>::~LinkedList() {
        // 析构释放内存 ?
        for(int i=0; i < len; i++){
            delete(node(i));
        }
    
        // 头指针和尾指针置为NULL
        first = NULL;
        last = NULL;
    }
    
    
    template<class E>
    void LinkedList<E>::linkLast(E e) {
        Node<E> *l = last;
        Node<E> *new_node = new Node<E>(e,l,NULL);
        last = new_node;
    
        if(l){
            l->next = new_node;
        } else
            first = new_node;
        len ++;
    }
    
    template<class E>
    void LinkedList<E>::linkBefore(Node<E> *pNode, E e) {
        Node<E> *pre = pNode->pre;// NULL
        Node<E> *new_node = new Node<E>(e,pre,pNode);
        // 当前节点的上一个节点 = 新增的节点
        pNode->pre = new_node;
        // 上一个节点的 next -> 新增的节点 , 0 特殊处理
        if(pre){
            pre->next = new_node;
        } else
            first = new_node;
        len ++;
    }
    
    template<class E>
    E LinkedList<E>::unlink(Node<E> *pNode) {
        E e = pNode->value;
        // 左右两个节点
        Node<E> *pre = pNode->pre;
        Node<E> *next = pNode->next;
    
        // 有两个为空的情况,严谨,思维灵活
        if(pre){
            pre->next = next;
            pNode->pre = NULL;
        } else
            first = next;
    
        if(next){
            next->pre = pre;
            pNode->next = NULL;
        }else
            last = pre;
    
        pNode -> value = NULL;
        delete pNode;
        len --;
        return e;
    }
    
    
    
    #endif //NDKPRACTICE_LINKEDLIST_HPP
    
    
    展开全文
  • 单链表与双链表知识点 链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。...
  • 单链表与双链表交换相邻结点比较 单链表结点结构体 typedef struct Listnode1{ //为单链表设置的结点结构体 int data; struct Listnode1 *next; }Listnode1; 双链表结点结构体 typedef struct Listnode2{ ...
  • 单链表与双链表队列

    2015-11-12 19:46:39
    一,链表分类:单链表与双向链表;  二,链表定义:数据域(data)与指针域(node)的下一个节点(next),头节点(head),上一个节点(pre);  三,定义类;  (1)Node类:传值与重写get,set方法;  (2)LinkNodeList类;将...
  • 数组与链表 数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),链表定位元素时间复杂度O(n);数组插入或删除元素的时间复杂度O(n),链表的时间复杂度O(1)。 ...
  • 单链表 双链表
  • C语言-基础入门-学习笔记(16):单链表与双链表 一、链表简介 我们都知道,数组虽然使用方便,但是有两个重要的缺陷: (1)数组内的元素类型必须相同。 (2)数组的元素个数在初始化之后就不能被改变了。 那么对于...
  • 双链表的创建(头插法、尾插法),单链表的插入、删除等 #include <stdio.h> #include <iostream> using namespace std; typedef int Elemtpye; typedef struct Lnode { Elemtpye data;//结点的...
  • 一、双向链表与单链表对比 1、单向链表,查找的方向只能是一个方向,而双向链表可以向前或者向后查找。 2、单向链表不能自我删除,需要靠辅助节点 ,而双向链表,则可以自我删除。所以前面我们单链表删除节点时,...
  • 实现一个单链表链表初始为空,支持三种操作: (1) 向链表头插入一个数; (2) 删除第k个插入的数后面的数; (3) 在第k个插入的数后插入一个数 现在要对该链表进行M次操作,进行完所有操作后,从头到尾输出整个链表...
  • 首先看单链表class Chain(): def __init__(self): self.first = None self.length = 0 def is_empty(self): """是否为空""" return self.first == None def add(self, val): """头部添加""" node = Node...
  • 昨天面试官面试的时候问了我一道关于链表的问题:情境如下 面试官:请说一下链表跟数组的区别? 我:数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),...
  • 昨天面试官面试的时候问了我一道关于链表的问题:情境如下 面试官:请说一下链表跟数组的区别? 我:数组静态分配内存,链表动态分配内存;数组在内存中连续,链表不连续;数组利用下标定位,时间复杂度为O(1),...
  • 1.1 什么是链表链表是有序的列表,但是它在内存中是存储如下 特点如下: 链表是以节点的方式来存储,是链式存储 每个节点包含 data 域, next 域:指向下一个节点. 如图:发现链表的各个节点不一定是连续存储....
  • 一、单链表中的循环链表: 目前我们的链表最后一个结点的pNext指向的是NULL;循环链表中的最后一个结点的pNext指向的是头结点; 循环链表和不是循环链表的区别:判断条件不一样! p->pNext == NULL; p->pNext ...
  • 链表跟数组的区别: 数组随机访问性强(通过下标进行快速定位),查找速度快; 链表不能随机查找,必须从第一个开始遍历,查找效率低 数组插入和删除效率低(插入和删除需要移动数据), 链表插入删除速度快(因为有...
  • 单链表 package main import "fmt" //单链表的基本使用 type HeroNode struct { No int Name string Nickname string NextNode *HeroNode } //像链表追加元素 func (this *HeroNode)AppendNode(node *...
  • 链表的基础操作,增删查插 感觉最重要的画出来,一步一步的分析,不要凭空想象,不要凭空想象,不要凭空想象 单链表: #include <stdio.h> #include <stdlib.h> #define bool int #define false 0 #...
  • 链表基本概念(详细内容可自己百度或查询相关书籍): 链表就是包含数据的独立数据结构的集合。链表中的每个节点通过链表或指针链接在一起,程序通过指针访问链表中的节点。 注: 链表的其他综合实践案例可到我的...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,783
精华内容 713
关键字:

单链表与双链表