• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            posts - 297,  comments - 15,  trackbacks - 0

            Doubly-linked list

            In computer science, a doubly-linked list is a linked data structure that

            consists of a set of data records, each having two special link fields that

            contain references to the previous and to the next record in the sequence.

            It can be viewed as twosingly-linked lists formed from the same data items, 

            in two opposite orders. A doubly-linked list whose nodes contains three fields:

                  an integer value, the link to the next node, and the link to the previous node.

            The two links allow walking along the list in either direction with equal ease.
            Compared to a singly-linked list, modifying a doubly-linked list usually requires
            changing more pointers, but is sometimes simpler because there is no need to
            keep track of the address of the previous node.

            Contents

             [hide]

            Nomenclature and implementationThe

            references stored in the link fields are

            usually implemented by pointers; but

            (as in any linked data structure) they may also be address offsets or indices into

            an array where the nodes live.

            The link fields are often called forward and backwards, or next and previous.

            A pointer to any node of a doubly-linked list gives access to the whole list. However,

            it's usually convenient to handle the list by the pointers of the first and last nodes,

            e.g. when passing it to subroutines.

            Basic algorithms

            Open doubly-linked lists

            Data type declarations

             record Node {
            data // The data being stored in the node
            next // A reference to the next node; null for last node
            prev // A reference to the previous node; null for first node
            }
             record List {
            Node firstNode // points to first node of list; null for empty list
            Node lastNode // points to last node of list; null for empty list
            }

            Iterating over the nodes

            Iterating through a doubly linked list can be done in either direction. In fact, direction can

            change many times, if desired.

            Forwards

             node := list.firstNode
            while node ≠ null
            <do something with node.data>
            node := node.next

            Backwards

             node := list.lastNode
            while node ≠ null
            <do something with node.data>
            node := node.prev

            Inserting a node

            These symmetric functions add a node either after or before a given node, with the

            diagram demonstrating after:

            Doubly linked list insert after.png
             function insertAfter(List list, Node node, Node newNode)
            newNode.prev := node
            newNode.next := node.next
            if node.next == null
            list.lastNode := newNode
            else
            node.next.prev := newNode
            node.next := newNode
             function insertBefore(List list, Node node, Node newNode)
            newNode.prev := node.prev
            newNode.next := node
            if node.prev is null
            list.firstNode := newNode
            else
            node.prev.next := newNode
            node.prev := newNode

            We also need a function to insert a node at the beginning of a possibly-empty list:

             function insertBeginning(List list, Node newNode)
            if list.firstNode == null
            list.firstNode := newNode
            list.lastNode := newNode
            newNode.prev := null
            newNode.next := null
            else
            insertBefore(list, list.firstNode, newNode)

            A symmetric function inserts at the end:

             function insertEnd(List list, Node newNode)
            if list.lastNode == null
            insertBeginning(list, newNode)
            else
            insertAfter(list, list.lastNode, newNode)

            Deleting a node

            Removing a node is easier, only requiring care with the firstNode and lastNode:

             function remove(List list, Node node)
            if node.prev == null
            list.firstNode := node.next
            else
            node.prev.next := node.next
            if node.next == null
            list.lastNode := node.prev
            else
            node.next.prev := node.prev
            destroy node

            One subtle consequence of this procedure is that deleting the last element of a list

            sets both firstNode and lastNode to null, and so it handles removing the last node

            from a one-element list correctly. Notice that we also don't need separate "removeBefore"

            or "removeAfter" methods, because in a doubly-linked list we can just use "remove(node.prev)"

            or "remove(node.next)" where these are valid.

            Circular Doubly-linked lists

            Iterating over the elements

            Assuming that someNode is some node in a non-empty list, this code iterates through

            that list starting with someNode (any node will do):

            Forwards

             node := someNode
            do
            do something with node.value
            node := node.next
            while node ≠ someNode

            Backwards

             node := someNode
            do
            do something with node.value
            node := node.prev
            while node ≠ someNode

            Notice the postponing of the test to the end of the loop. This is important for the

            case where the list contains only the single node someNode.

            Inserting a node

            This simple function inserts a node into a doubly-linked circularly-linked list after

            a given element:

             function insertAfter(Node node, Node newNode)
            newNode.next := node.next
            newNode.prev := node
            node.next.prev := newNode
            node.next := newNode

            To do an "insertBefore", we can simply "insertAfter(node.prev, newNode)". Inserting

            an element in a possibly empty list requires a special function:

             function insertEnd(List list, Node node)
            if list.lastNode == null
            node.prev := node
            node.next := node
            else
            insertAfter(list.lastNode, node)
            list.lastNode := node

            To insert at the beginning we simply "insertAfter(list.lastNode, node)". Finally,

            removing a node must deal with the case where the list empties:

             function remove(List list, Node node)
            if node.next == node
            list.lastNode := null
            else
            node.next.prev := node.prev
            node.prev.next := node.next
            if node == list.lastNode
            list.lastNode := node.prev;
            destroy node


            References

            See also

            from wikipedia:
            http://en.wikipedia.org/wiki/Doubly-linked_list
            posted on 2011-01-02 12:04 chatler 閱讀(827) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
            <2025年7月>
            293012345
            6789101112
            13141516171819
            20212223242526
            272829303112
            3456789

            常用鏈接

            留言簿(10)

            隨筆分類(307)

            隨筆檔案(297)

            algorithm

            Books_Free_Online

            C++

            database

            Linux

            Linux shell

            linux socket

            misce

            • cloudward
            • 感覺這個博客還是不錯,雖然做的東西和我不大相關,覺得看看還是有好處的

            network

            OSS

            • Google Android
            • Android is a software stack for mobile devices that includes an operating system, middleware and key applications. This early look at the Android SDK provides the tools and APIs necessary to begin developing applications on the Android platform using the Java programming language.
            • os161 file list

            overall

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            日韩欧美亚洲综合久久影院Ds | 久久亚洲国产精品123区| 77777亚洲午夜久久多喷| 97久久国产亚洲精品超碰热| 国产精品久久久久jk制服| 亚洲成人精品久久| 久久久久成人精品无码| 亚洲伊人久久精品影院| 国产日产久久高清欧美一区| 国产激情久久久久影院小草| 国产69精品久久久久观看软件| 亚洲精品无码久久久影院相关影片| 久久精品国产亚洲av高清漫画| 天天爽天天爽天天片a久久网| 亚洲国产成人久久精品99 | 国产精品久久久天天影视| 久久本道久久综合伊人| 99久久国产宗和精品1上映| 亚洲国产精品久久久久| 亚洲色大成网站WWW久久九九| 久久99中文字幕久久| 欧美一区二区久久精品| 国产精品丝袜久久久久久不卡| 国产精品99久久久久久宅男小说| 国产精品久久久久久福利漫画| 亚洲国产成人久久综合区| 国产精品VIDEOSSEX久久发布| 天天躁日日躁狠狠久久 | 久久久久亚洲AV无码网站| 久久久久人妻精品一区三寸蜜桃| 久久久久女人精品毛片| 亚洲午夜久久久| 欧美亚洲日本久久精品| 99久久婷婷国产一区二区| 高清免费久久午夜精品| 久久99精品久久只有精品| 国产精品一区二区久久精品涩爱| 久久综合精品国产一区二区三区 | 久久国产精品偷99| 精品乱码久久久久久夜夜嗨| 国产女人aaa级久久久级|