精华内容
下载资源
问答
  • //双向链表和单链表的区别及其初始化 //相比单链表,多了一个前驱指针域 //初始化的时候,多了一步(详见初始化函数) typedef struct lNode { int data; //数据域 struct lNode *ne...
    #include <iostream>
    #include <cstdlib>
    using namespace std;
    
    //双向链表和单链表的区别及其初始化
    //相比单链表,多了一个前驱指针域
    //初始化的时候,多了一步(详见初始化函数)
    
    typedef struct lNode
    {
        int data;    //数据域
        struct lNode *next;  //后继指针域
        struct lNode *prior; //前驱指针域 
    }LNode, *LinkList;
    
    /******************初始化双向链表*************************/
    void InitList(LinkList &l)
    {
        //初始化生成一个{1,2,3,4,5,6}这样的单链表
        LinkList p , q;
        //成功创建一个头结点(空结点)
        l = (LinkList)malloc(sizeof(LinkList));
        l->next=NULL;
        p=l;
        //开始生成单链表(尾插法,每次插入在最后一个结点后面进行)
        for(int i=1 ; i<=6 ; i++)
        {
            q=(LinkList)malloc(sizeof(LinkList));
            q->data=i;
            p->next =q;
            q->prior=p;  //区别1:与单链表的区别多在这一步
            p=q;
            p->next=NULL;
        }
    }
    
    /******************显示双向链表*************************/
    void Showlist(LinkList &l)
    {
        LinkList p,r;
        //正向显示
        for(p=l->next;p!=NULL;p=p->next)
        {
            cout<<p->data<<"  ";
            r=p; //起标志作用,方便后面反向输出
        }
        cout<<endl;
        //反向显示
        for(r;r!=l;r=r->prior)
            cout<<r->data<<"  ";
    }
    
    int main()
    {
        LinkList l ;
        InitList(l);
        Showlist(l);
        return 0;
    }
    
    
    展开全文
  • 文章目录带头结点的双向循环链表和单链表的区别面试题:写一个双向链表代码实现 带头结点的双向循环链表和单链表的区别   相比我们讲的无头单向非循环的单链表结构,他的插入和删除都是O(1),也不需要增容,浪费...

    带头结点的双向循环链表和单链表的区别

      相比我们讲的无头单向非循环的单链表结构,他的插入和删除都是O(1),也不需要增容,浪费空间换取时间,但是需要申请和释放空间。

    面试题:写一个双向链表

    思路
      主要实现函数ListInsert,ListFind,ListErase,其他的函数如头插,尾插,头删,尾删等函数可以用以上几个关键的函数代替实现。

    代码实现

    void ListPushFront(ListNode* phead, LTDataType x)
    {
    	assert(phead);
    	ListNode* node = (ListNode*)malloc(sizeof(ListNode*));
    	node->val = x;
    
    	ListNode* next = head->next;
    	node->next = next;
    	head->next = node;
    	next->prev = node;
    	node->prev = head;
    }
    
    void ListPopBack(ListNode* phead)
    {
    	assert(phead);
    	assert(phead->next != head);
    
    	ListNode* tail = phead->prev;
    	ListNode* tailPrev = tail->prev;
    
    	free(tail);
    	tailPrev->next = phead;
    	phead->prev = tailPrev;
    }
    
    void ListPopFront(ListNode* phead)
    {
    	assert(phead);
    	assert(phead->next != head);
    
    	ListNode* node = phead->next;
    	ListNode* next = node->next;
    	head->next = next;
    	next->prev = head;
    	free(node);
    }
    
    void ListInsert(ListNode* phead, LTDataType x)
    {
    	assert(pos);
    	ListNode* newNode = BuyListNode(x);
    	ListNode posPrev = pos->prev;
    
    	posPrev->next = newNode;
    	newNode->next = pos;
    	pos->prev = newNode;
    	newNode->prev = posPrev;
    }
    
    void ListFind(ListNode* phead, LTDataType x)
    {
    	assert(phead);
    
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		if (cur->data == x)
    		{
    			retrun cur;
    		}
    		cur = cur->next;
    	}
    	return NULL;
    }
    
    void ListErase(ListNode* pos)
    {
    	assert(pos);
    	//pos不能是phead,否则头结点没了
    	//assert(pos != phead);
    
    	ListNode* posPrev = pos->prev;
    	ListNode* posNext = pos->next;
    
    	posPrev->next = posNext;
    	posNext->prev = posPrev;
    	free(pos);
    }
    
    void ListDestory(ListNode* phead)
    {
    	ListNode* cur = phead->next;
    	while (cur != phead)
    	{
    		ListNode* next = cur->next;
    		ListErase(cur);
    		cur = next;
    	}
    	free(phead);0
    }
    
    展开全文
  • 链表 单链表 单链表的每个节点由连接到下个节点的引用及值组成,通过引用字段将每个节点按一定顺序连接起来。 单链表节点结构 struct SinglyListNode { int val; SinglyListNode *next; SinglyListNode(int x) :...

    链表

    单链表

    单链表的每个节点由连接到下个节点的引用及值组成,通过引用字段将每个节点按一定顺序连接起来。

    单链表节点结构

    在这里插入图片描述

    struct SinglyListNode {
        int val;
        SinglyListNode *next;
        SinglyListNode(int x) : val(x), next(NULL) {}
    };
    

    同数组不同,要想访问链表中的某个元素,必须从头结点逐个遍历。 其时间复杂度为 O(N) ,其中 N 是链表的长度

    设计链表

    1. 链表初始化–>MyLinkedList()
    2. 在链表的第一个元素前添加链表节点(头插)–>addAtHead
    3. 在链表最后一个元素后添加新节点(尾插)–>addAtTail
    4. 在链表的第index个节点前添加节点–>addAtIndex
    5. 查找节点–>get
    6. 遍历节点–>
    7. 删除指定节点–>deleteAtIndex
    8. 获取链表长度–>
    9. 销毁链表–>
      code:
    #include <stdio.h>
    
    #define CRTDBG_MAP_ALLOC    
    #include <stdlib.h>    
    #include <crtdbg.h> 
    
    #ifdef _DEBUG
    #ifndef DBG_NEW
    #define DBG_NEW new ( _NORMAL_BLOCK , __FILE__ , __LINE__ )
    #define new DBG_NEW
    #endif 
    #endif  // _DEBUG
    
    
    class MyLinkedList {
    private:
    	struct LinkedNode {
    		int val;
    		LinkedNode* next;
    		LinkedNode(int val) :val(val), next(NULL) {}
    	};
    	int _size;
    	LinkedNode* _dummyHead;
    public:
    
    	/** Initialize your data structure here. */
    	MyLinkedList() {
    		_dummyHead = new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点,而不是真正的链表头结点
    		_size = 0;
    	}
    
    	~MyLinkedList()
    	{
    		delete _dummyHead;
    	}
    	/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    	int get(int index) {
    		if (index > (_size - 1) || index < 0)  return -1;
    		LinkedNode* cur = _dummyHead->next;
    		while (index--)
    		{
    			cur = cur->next;
    		}
    		return cur->val;
    	}
    
    	/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
    	void addAtHead(int val) {
    		LinkedNode* cur = new LinkedNode(val);
    		cur->next = _dummyHead->next;
    		_dummyHead->next = cur;
    		_size++;
    	}
    
    	/** Append a node of value val to the last element of the linked list. */
    	void addAtTail(int val) {
    		LinkedNode* cur = new LinkedNode(val);
    		LinkedNode* head = _dummyHead;
    		while (head->next != NULL)
    		{
    			head = head->next;
    		}
    		head->next = cur;
    		_size++;
    	}
    
    	/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
    	void addAtIndex(int index, int val) {
    		if (index > _size)   return;
    		LinkedNode* head = _dummyHead;
    		LinkedNode* cur = new LinkedNode(val);
    		while (index--)
    		{
    			head = head->next;
    		}
    		cur->next = head->next;
    		head->next = cur;
    		_size++;
    	}
    
    	/** Delete the index-th node in the linked list, if the index is valid. */
    	void deleteAtIndex(int index) {
    		if (index >= _size || index < 0) return;
    
    		LinkedNode* head = _dummyHead;
    		while (index--) {
    			head = head->next;
    		}
    		LinkedNode* tmp = head->next;
    		head->next = head->next->next;
    		delete tmp;
    		_size--;
    	}
    	void travel()
    	{
    		LinkedNode* head = _dummyHead;
    		while (head->next != NULL)
    		{
    			head = head->next;
    			printf("%d\n", head->val);
    		}
    	}
    
    	void distory()
    	{
    		LinkedNode* head = _dummyHead;
    		while (head->next != NULL)
    		{
    			LinkedNode* tmp = head->next;
    			head->next = head->next->next;
    			delete tmp;
    		}
    	}
    
    	int getLength()
    	{
    		int length = 0;
    		LinkedNode* head = _dummyHead;
    		while (head != NULL)
    		{
    			head = head->next;
    			length++;
    		}
    		return length;
    	}
    };
    
    /**
     * Your MyLinkedList object will be instantiated and called as such:
     * MyLinkedList* obj = new MyLinkedList();
     * int param_1 = obj->get(index);
     * obj->addAtHead(val);
     * obj->addAtTail(val);
     * obj->addAtIndex(index,val);
     * obj->deleteAtIndex(index);
     */
    int main()
    {
    	MyLinkedList* obj = new MyLinkedList();
    	//int param_1 = obj->get(index);
    	obj->addAtHead(1);
    	obj->addAtHead(2);
    	obj->addAtHead(3);
    	obj->addAtHead(4);
    	obj->addAtTail(6);
    	obj->travel();
    	printf("-----------------------");
    	obj->addAtIndex(3,99);
    	obj->deleteAtIndex(2);
    	obj->travel();
    	printf("-----------------------");
    	int len = obj->getLength();
    	printf("%d\n", len);
    	
    	obj->distory();
    	delete obj;
    	_CrtDumpMemoryLeaks();
    }
    

    双链表

    在这里插入图片描述

    双链表结构
    struct Dnode {
    int val;
    Dnode* prev;
    Dnode* next;
    Dnode(int x) :val(x), next(NULL), prev(NULL) {}
    };
    设计链表:

    1. 链表初始化–>MyLinkedList()
    2. 在链表的第一个元素前添加链表节点(头插)–>addAtHead
    3. 在链表最后一个元素后添加新节点(尾插)–>addAtTail
    4. 在链表的第index个节点前添加节点–>addAtIndex
    5. 查找节点–>get
    6. 遍历节点–>travel
    7. 删除指定节点–>deleteAtIndex
    8. 获取链表长度–>getLength
    9. 销毁链表–>destory

    code:

    #include <stdio.h>
    
    #define CRTDBG_MAP_ALLOC    
    #include <stdlib.h>    
    #include <crtdbg.h> 
    
    #ifdef _DEBUG
    #ifndef DBG_NEW
    #define DBG_NEW new ( _NORMAL_BLOCK , __FILE__ , __LINE__ )
    #define new DBG_NEW
    #endif 
    #endif  // _DEBUG
    
    class MyLinkedList {
    private:
        struct Dnode {
            int val;
            Dnode* prev;
            Dnode* next;
            Dnode(int x) :val(x), next(NULL), prev(NULL) {}
        };
        Dnode* _dummyHead;
        Dnode* _dummyTail;
        int _size;
    public:
        /** Initialize your data structure here. */
        MyLinkedList() {
            _dummyHead = new Dnode(0);
            _dummyTail = new Dnode(0);
            _dummyHead->next = _dummyTail;
            _dummyTail->prev = _dummyHead;
            _size = 0;
        }
    
        /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
        int get(int index) {
            if (index >= _size || index < 0) return -1;
            //通过比较 index 和 size - index 判断距离头节点近还是尾节点近
            Dnode* cur = _dummyHead;
            if (index + 1 < _size - index)
            {
                for (int i = 0; i < index + 1; ++i) cur = cur->next;
            }
            else
            {
                cur = _dummyTail;
                for (int i = 0; i < _size - index; ++i) cur = cur->prev;
            }
            return cur->val;
        }
    
        /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
        void addAtHead(int val) {
            ++_size;
            Dnode* addNode = new Dnode(val);
            Dnode* cur = _dummyHead->next;
            addNode->next = _dummyHead->next;
            addNode->prev = _dummyHead;
            cur->prev = addNode;
            _dummyHead->next = addNode;
        }
    
        /** Append a node of value val to the last element of the linked list. */
        void addAtTail(int val) {
            _size++;
            Dnode* addNode = new Dnode(val);
            Dnode* cur = _dummyTail->prev;
            addNode->next = _dummyTail;
            addNode->prev = cur;
            _dummyTail->prev = addNode;
            cur->next = addNode;
        }
    
        /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
        void addAtIndex(int index, int val) {
            if (index > _size) return;
            if (index < 0) index = 0;
            Dnode* newNode = new Dnode(val);
            Dnode* cur = NULL, * pre = NULL, * succ = NULL;
            if (index + 1 < _size - index)
            {
                cur = _dummyHead;
                for (int i = 0; i < index + 1; ++i)
                {
                    cur = cur->next;
                }
            }
            else
            {
                cur = _dummyTail;
                for (int i = 0; i < _size - index; ++i)
                {
                    cur = cur->prev;
                }
            }
            pre = cur->prev;
            succ = cur;
    
            newNode->next = succ;
            newNode->prev = pre;
            succ->prev = newNode;
            pre->next = newNode;
            _size++;
        }
    
        /** Delete the index-th node in the linked list, if the index is valid. */
        void deleteAtIndex(int index) {
            if (index < 0 || index >= _size) return;
            Dnode* cur = _dummyHead;
            Dnode* pre;
            Dnode* succ;
            Dnode* deleteNode;
            if (index + 1 < _size - index)
            {
                for (int i = 0; i < index + 1; ++i)
                {
                    cur = cur->next;
                }
            }
            else
            {
                cur = _dummyTail;
                for (int i = 0; i < _size - index; ++i)
                {
                    cur = cur->prev;
                }
            }
            deleteNode = cur;
    
            pre = cur->prev;
            succ = cur->next;
            succ->prev = pre;
            pre->next = succ;
    
            delete deleteNode;
            deleteNode = NULL;
            _size--;
        }
    
        void travelHead()
        {
            Dnode* head = _dummyTail->prev;
            while (head != NULL)
            {
                printf("%d", head->val);
                head = head->prev;
            }
        }
    
        void travelNext()
        {
            Dnode* head = _dummyHead->next;
            while (head != NULL)
            {
                printf("%d",head->val);
                head = head->next;
            }
        }
    
        void distory()
        {
            Dnode* head = _dummyHead;
            while (head->next != NULL)
            {
                Dnode* tmp = head->next;
                head->next = head->next->next;
                delete tmp;
    
            }
        }
    
        int getLength()
        {
            int length = 0;
            Dnode* head = _dummyHead;
            while (head != NULL)
            {
                head = head->next;
                length++;
            }
            return length;
        }
    };
    
    /**
     * Your MyLinkedList object will be instantiated and called as such:
     * MyLinkedList* obj = new MyLinkedList();
     * int param_1 = obj->get(index);
     * obj->addAtHead(val);
     * obj->addAtTail(val);
     * obj->addAtIndex(index,val);
     * obj->deleteAtIndex(index);
     */
    
    
    int main()
    {
    
        MyLinkedList* obj = new MyLinkedList();
        //int param_1 = obj->get(index);
        obj->addAtHead(1);
        obj->addAtHead(2);
        obj->addAtHead(3);
        obj->addAtHead(4);
        obj->addAtTail(6);
        obj->travelHead();
        printf("-----------------------");
        obj->addAtIndex(3, 9);
        obj->deleteAtIndex(2);
        obj->travelNext();
    
        printf("-----------------------");
        int len = obj->getLength();
        printf("%d\n", len);
    
    
        obj->distory();
        delete obj;
        _CrtDumpMemoryLeaks();
    }
    
    
    展开全文
  • 双向链表单链表

    2013-09-11 15:55:51
    双链表就是双向链表,就是在单链表的每个结点里再增加一个指向...双链表上的插入删除时间复杂度均为O (1)。 ************************************************************ 单链表运算:·建立单链表·头插法:s->
    双链表就是双向链表,就是在单链表的每个结点里再增加一个指向其直接前趋的指针域prior,形成两条不同方向的链。由头指针head惟一确定。
    双链表也可以头尾相链接构成双(向)循环链表。
    双链表上的插入和删除时间复杂度均为O (1)。

    ************************************************************
    单链表运算:·建立单链表·头插法:s->next=head;head=s;生成的顺序与输入顺序相反。平均时间复杂度均为O(n)。
    ·尾插法:head=rear=null;if(head=null) head=s;else r->next=s;r=s; 平均时间复杂度均为O(n)
    ·加头结点的算法:对开始结点的操作无需特殊处理,统一了空表和非空表。
    ·查找·按序号:与查找位置有关,平均时间复杂度均为O(n)。
    ·按值:与输入实例有关,平均时间复杂度均为O(n)。
    ·插入运算:p=GetNode(L,i-1);s->next=p->next;p->next=s;平均时间复杂度均为O(n)
    ·删除运算:p=GetNode(L,i-1);r=p->next;p->next=r->next;free(r);平均时间复杂度均为O(n)
    ************************************************************
    单循环链表是一种首尾相接的单链表,终端结点的指针域指向开始结点或头结点。链表终止条件是以指针等于头指针或尾指针。
    采用单循环链表在实用中多采用尾指针表示单循环链表。优点是查找头指针和尾指针的时间都是O(1),不用遍历整个链表。
    展开全文
  • JavaScript数据结构之链表(单链表,翻转单链表双链表,循环链表) 链表是一种存储数据的工具,不同于数组,链表中的元素并不是连续存储的,因此不能通过下标去访问。 链表分为单(向)链表,双向链表,循环链表等 ...
  • } } //以下实现的是单链表,没有了双链表的head头指针的哑元(空元素),但必须构造一个tail尾结点辅助。 /* * To change this template, choose Tools | Templates * and open the template in the editor. */ ...
  • 在创建单链表时如果使用使用动态的单链表,那么每创建一个结点时就会使用new 当数据比较大的时候,程序运行的时间很长 所以在写题的时候 往往会那数组来模拟一个链表; 先进行如下定义: head为头结点的头指针; idx...
  • 单链表 1.1 插入 实现在aiai+1中间插入e(固定套路): e —> ai+1 ai—> e e.next = ai.next; ai.next = e; 1.2 删除节点 实现ai的删除: ai-1.next = ai-1.next.next; 二 双向链表 注意:此时理解...
  • Java-链表1、什么是链表?2、链表的特点是什么?3、链表的实现原理?4、如何自己写出一个链表?1、什么是链表链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针连接次序...
  • 单链表定义,相关操作以及代码实现(JAVA) 双向链表定义,相关操作以及代码实现(JAVA) 单向环形链表定义,相关操作以及代码实现(JAVA) Josephu 问题(约瑟夫问题)
  • 您可以选择使用单链表双链表单链表中的节点应该具有两个属性:val next。val 是当前节点的值,next 是指向下一个节点的指针/引用。如果要使用双向链表,则还需要一个属性 prev 以指示链表中的上一个节点。...
  • //以下实现的是单链表,没有了双链表的head头指针的哑元(空元素),但必须构造一个tail尾结点辅助。 /* * To change this template, choose Tools | Templates * and open the template in the editor. */...
  • 循环链表2.1 循环单链表2.2 循环双链表2.3 循环链表判空2.3.1 循环单链表2.3.2 循环双链表3. 静态链表4. 顺序表与链表比较4.1 存取方式4.2 逻辑结构、物理结构4.3 基本操作4.4 内存空间总结4.5 怎样选择线性表的...
  • 链表(单链表和双链表

    千次阅读 2012-04-17 18:42:00
    单链表创建及操作 #include #include typedef struct node//定义节点 { int data; struct node *next; }Node,*Link;//struct node a,*p->typedef struct node Node,*Link Link Create_Link()//将节点...
  • 简单的说,链表就是由多个结点离散分配,彼此通过指针相连,每个结点只有一个前驱结点后继结点。首节点无前驱结点,为结点无后继结点的一种存储结构。 链表的结构 头结点:链表的第一个有效结点前面...
  • 为方便自己记录学习过的资料,以便更好的复习学习:  循环链表---http://blog.csdn.net/ab198604/article/details/8465220 单向链表--http://blog.csdn.net/ab198604/article/details/8253405 双向链表--...
  • 链表单链表

    2017-10-16 16:18:40
    循环链表和单链表不同的是最后一个元素的指针域指向了头节点。 双向链表的节点有三部分,其中两部分是指针域。一个指向前一个节点,一个指向后一个节点。 有的语言没有指针,要用到静态链表。 实现方法类似于...
  • 我们知道,数组作为数据存储结构有一定的...这里主要来讨论并写一个单链表和双向链表。 顾名思义,单链表只能从表头到表尾的顺序,每个节点中保存了指向下一个节点的指针; 双向链表则可以反向遍历,因为节点中既...
  • 链表-单链表

    2020-11-24 17:08:38
    链表可分为单链表双链表、循环链表和静态链表。 1. 单链表 1.1 单链表定义 单链表中每个数据内存中不只存放着单个元素的数据元素,还存放着指向下一个节点的指针。 1.1.1 单链表定义代码 //c++代码 struct LNode {...
  • 题号1:分别以单链表、循环链表、双向链表为例,实现线性表的建立、插入、删除、查找等基本操作。 要求:能够把建立、插入、删除等基本操作的过程随时显示输出来。 1.2 软件功能 功能分为三个板块,分别是单链表...
  • 单链表是最常用的链表,其对数据的操作均为单项的,向后查找的。 /* 链表(基于对象) 此处为单链表 */ function Node (ele) { this.element = ele; this.next = null; } functio...

空空如也

空空如也

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

双链表和单链表