• <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 閱讀(830) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
            <2011年1月>
            2627282930311
            2345678
            9101112131415
            16171819202122
            23242526272829
            303112345

            常用鏈接

            留言簿(10)

            隨筆分類(307)

            隨筆檔案(297)

            algorithm

            Books_Free_Online

            C++

            database

            Linux

            Linux shell

            linux socket

            misce

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

            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

            搜索

            •  

            最新評論

            閱讀排行榜

            評論排行榜

            色偷偷偷久久伊人大杳蕉| 波多野结衣久久| 精品久久久久久中文字幕大豆网 | 国产精品午夜久久| 久久无码人妻精品一区二区三区| 久久97久久97精品免视看秋霞| 理论片午午伦夜理片久久| 综合久久一区二区三区| 久久精品国产亚洲AV电影| 国产精品99久久久久久董美香| 久久久久久毛片免费看| 久久综合狠狠色综合伊人| 一本色道久久88综合日韩精品 | 国产L精品国产亚洲区久久| 最新久久免费视频| 精品无码久久久久久久动漫| 亚洲色欲久久久综合网东京热| 久久精品国产99国产精品澳门| 精品多毛少妇人妻AV免费久久| 久久线看观看精品香蕉国产| 久久99九九国产免费看小说| 99久久精品国产综合一区 | 亚洲精品无码久久一线| 久久av高潮av无码av喷吹| 久久久精品国产sm调教网站| 久久天天躁狠狠躁夜夜不卡| 欧美国产精品久久高清| 国产综合精品久久亚洲| 国产精品久久久久久影院| 久久天天躁狠狠躁夜夜网站 | 久久亚洲国产欧洲精品一| 日日躁夜夜躁狠狠久久AV| 精品一二三区久久aaa片| 日韩亚洲国产综合久久久| 日本精品久久久中文字幕| 粉嫩小泬无遮挡久久久久久| 国产精品18久久久久久vr| 久久精品亚洲精品国产色婷 | 久久午夜无码鲁丝片午夜精品| 久久夜色tv网站| 国产精品欧美久久久久天天影视|