LinkedList (Swift)

연결 리스트 - 위키백과, 우리 모두의 백과사전

링크드 리스트 구조

• 연결 리스트
• 배열은 순차적으로 연결된 공간에 데이터를 나열하는 데이터 구조
• 링크드 리스트는 떨어진 곳에 존재하는 데이터를 포인터를 이용해 연결해서 관리하는 데이터 구조
• 미리 데이터 공간을 할당할 필요가 없음
• 배열에 비해 다음 노드 위치를 저장할 공간 필요
• 배열에 있는 index가 없어서 direct access가 안됨 (접근 속도 느림)
•  
• Doubly Linked List (양방향)

노드

class Node<T: Equatable> : Equatable {
    var prev : Node?
    var next : Node?
    var value : T
    
    init(value : T) {
        self.value = value
    }
    
    static func == (lhs: Node<T>, rhs: Node<T>) -> Bool {
        return lhs.prev == rhs.prev && lhs.next == rhs.next && lhs.value == rhs.value
    }
}

노드 순회, 출력 (prev, curr, next)

func printLinkedList(head : Node) {
    var curr = head
    while curr.next != nil {
        print(curr.prev?.value ?? -1, curr.value, curr.next?.value ?? -1)
        curr = curr.next!
    }
    print(curr.prev?.value ?? -1, curr.value, curr.next?.value ?? -1)
    print("")
}

 노드 추가하기

꼬리에 추가 (tail 사용X)

func addTail(head: Node, newNode : Node){
    var curr = head
    while curr.next != nil {
        curr = curr.next!
    }
    curr.next = newNode
    newNode.prev = curr
}

let head = Node(value: 0)
addTail(head: head, newNode: Node(value: 1))
addTail(head: head, newNode: Node(value: 2))
addTail(head: head, newNode: Node(value: 3))
printLinkedList(head: head)


//-1 0 1
//0 1 2
//1 2 3
//2 3 -1

특정 값 뒤에 추가

func insertAfter(node: Node, newNode: Node) {
    var curr = head
    while curr.next != nil {
        if curr.value == node.value {
            // curr.prev curr         next.prev  curr.next(next)
            // curr.prev newNode.prev newNode    newNode.next
            let next = curr.next
            curr.next = newNode
            newNode.prev = curr
            newNode.next = next
            next?.prev = newNode
            break
        }else {
            curr = curr.next!
        }
    }
}

 

등등 예제

Design Linked List - LeetCode

import Foundation

class MyLinkedList {
    
    class Node {
        var prev : Node?
        var next : Node?
        var value : Int
        init(value : Int) {
            self.value = value
        }
    }
    
    var head : Node = Node(value: -1)
    var tail : Node = Node(value: -1)
    var size = 0
    
    /** Initialize your data structure here. */
    init() {
        head.next = tail
        tail.prev = head
    }
    
    /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
    func get(_ index: Int) -> Int {
        guard size > index && index >= 0 else {
            return -1
        }
        var curr = head.next
        var i = 0
        while curr?.next != nil {
            if i == index {
                return curr!.value
            }
            curr = curr?.next
            i += 1
        }
        return -1
    }
    
    /** 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. */
    func addAtHead(_ val: Int) {
        let newNode = Node(value: val)
        /// head newNode head.next head.next.next
        newNode.next = head.next
        newNode.prev = head
        head.next?.prev = newNode
        head.next = newNode
        size += 1
    }
    
    /** Append a node of value val to the last element of the linked list. */
    func addAtTail(_ val: Int) {
        let newNode = Node(value: val)
        /// tail.prev.prev tail.prev newNode tail
        newNode.next = tail
        newNode.prev = tail.prev
        tail.prev?.next = newNode
        tail.prev = newNode
        size += 1
    }
    
    /** 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. */
    func addAtIndex(_ index: Int, _ val: Int) {
        var i = 0
        var curr = head
        while curr.next != nil {
            if i == index {
                // curr newNode curr.next
                let newNode = Node(value: val)
                let next = curr.next
                curr.next = newNode
                newNode.prev = curr
                newNode.next = next
                next?.prev = newNode
            }
            curr = curr.next!
            i += 1
        }
        size += 1
    }
    
    /** Delete the index-th node in the linked list, if the index is valid. */
    func deleteAtIndex(_ index: Int) {
        var curr = head.next
        var i = 0
        while curr?.next != nil {
            if i == index {
                /// curr.prev curr curr.next
                curr?.prev?.next = curr?.next
                curr?.next?.prev = curr?.prev
            }
            curr = curr?.next
            i += 1
        }
    }
    func printLinkedList() {
        var curr = head
        while curr.next != nil {
            print("\(curr.value) -> ", terminator: "")
            curr = curr.next!
        }
        print()
    }
}