使用 scala 实现双向链表

港控/mmm° 2023-06-23 14:24 43阅读 0赞

双向链表也叫双链表。双向链表中不仅有指向后一个节点的指针，还有指向前一个节点的指针。这样可以从任何一个节点访问前一个节点，当然也可以访问后一个节点，以至整个链表。  
一般是在需要大批量的另外储存数据在链表中的位置的时候用。双向链表也可以  
![在这里插入图片描述][20191219194551826.png]

package com.atguigu.datastruc.linked_list
    
    /** * Author lzc * Date 2019-11-27 11:11 */
    object DoublyLinkedListDemo { 
        def main(args: Array[String]): Unit = { 
            val list = new DoublyLinkedList[Int]()
            list.add(10)
            list.add(20)
            list.add(30)
            
            list.printInfo()
            list.delete(30)
            list.delete(20)
            list.delete(10)
            list.printInfo()
        }
    }
    
    class DoublyLinkedList[T] { 
        
        var head: Node = _
        var tail: Node = _
        
        /** * 删除节点 * 双向节点删除比较方便: 支持自删除 * * @param ele */
        def delete(ele: T): Boolean = { 
            // 找到要删除的节点
            val targetNode: Node = find(ele)
            if (targetNode == null) {  // 如果要删除的节点不存在
                false
            }
            else {  // 删除的节点存在
                // 上一个节点
                val preNode: Node = targetNode.pre
                val nextNode: Node = targetNode.next // 下一个节点
                
                if (targetNode == head) {  // 如果是头节点
                    if (nextNode != null) nextNode.pre = null // 下一个节点的 pre 指向 null
                    head = nextNode // 更新头节点
                } else if (targetNode == tail) {  // 如果是尾节点
                    preNode.next = null // 上一个节点的 next 指向 null
                    tail = preNode // 更新尾节点
                } else { 
                    preNode.next = nextNode
                    nextNode.pre = preNode
                }
                true
            }
        }
        
        /** * 找到要删除的元素所在的节点 * * @param ele */
        protected def find(ele: T): Node = { 
            var tmp: Node = head // 从头节点开始查找
            while (tmp != null) { 
                if (tmp.value == ele) return tmp
                tmp = tmp.next
            }
            null
        }
        
        /** * 新增节点 * * @param ele */
        def add(ele: T): Boolean = { 
            val newNode: Node = Node(ele, null, null)
            if (head == null) {  // 第一次添加
                head = newNode // 因为第一个元素, 上一个和下一个节点都应该是 null
                
            } else {  // 不是第一次添加, tail 的next节点指向新节点, 新节点的pre节点指向 tail
                tail.next = newNode
                newNode.pre = tail
            }
            // 更新 tail 的指向
            tail = newNode
            true
        }
        
        
        /** * 打印链表的元素 */
        def printInfo(): Unit = { 
            if (head == null) return
            
            var tmp: Node = head
            do { 
                print(tmp.value + "->")
                tmp = tmp.next
            } while (tmp != null)
            
            println()
        }
        
        case class Node(value: T, var pre: Node, var next: Node)
        
    }

[20191219194551826.png]: https://img-blog.csdnimg.cn/20191219194551826.png