연결리스트의 종류

• 1. singly linked list 단일 연결 리스트
     
• 2. doubly linked list 다중 연결 리스트
     

개별 노드 삭제하기

1. 맨 처음 노드 삭제할 때 head와 previous 업데이트
2. 중간 노드 삭제할 때 previous와 next 업데이트
3. 맨 마지막 노드 삭제할 때 next와 tail 업데이트
   

• 1. 노드 생성하기
  • 초기화 시, 노드는 값을 가져야 하고
  • previous, next 포인터가 있다.
• 2. 연결 리스트 기능 구현하기
  • head, tail 노드로 구성되어 있다고 생각한다
  • append 연결리스트에 이미 값이 있었을 때와 없었을 때를 나눠서 생각해야 한다
  • nodeAt(index:) index가 0보다 크거나 같을 때 index를 1씩 감소시키면서 0이 될 때의 노드 리턴하기
  • removeAll next 포인터의 값을 저장할 때 첫번째 노드인지 아닌지, previous 포인터의 값을 저장할 때 마지막 노드인지 아닌지 생각해야한다.

//노드는 참조값이 필요해서 클래스를 사용했고
//클래스는 init이 필수인데 value가 있어야 하도록 만들었다
public class Node<T> {
    var value: T
    var next: Node<T>?
    weak var previous: Node<T>?
    
    init(value: T) {
        self.value = value
    }
}

public class LinkedList<T> {
    fileprivate var head: Node<T>?
    private var tail: Node<T>?
    
    public var isEmpty: Bool {
        return head == nil
    }
    
    public var first: Node<T>? {
        return head
    }
    
    public var last: Node<T>? {
        return tail
    }
    
    public func append(value: T) {
        let newNode = Node(value: value)    //노드 생성
        
        // 새로운 노드의 앞부분 연결하기
        if let tailNode = tail {	// 연결리스트에 값이 있는 경우
            newNode.previous = tailNode
            tailNode.next = newNode
        } else {	// 연결리스트에 값이 없는 경우
            head = newNode
        }
        
        // 새로운 노드의 뒷부분 연결하기
        tail = newNode
    }
    
    public func nodeAt(index: Int) -> Node<T>? {
        if index >= 0 {
            var node = head
            var i = index
            
            while node != nil {
                if i == 0 {
                    return node
                }
                i -= 1
                node = node!.next
            }
        }
        return nil
    }
    
    public func removeAll() {
        head = nil
        tail = nil
    }
    
    public func remove(node: Node<T>) -> T {
        let prev = node.previous
        let next = node.next
        
        // next 포인터의 값 저장
        if let prev = prev {    // 첫번째 노드가 아닐 때
            prev.next = next
        } else {                // 첫번째 노드일 때
            head = next
        }
        
        // prev 포인터의 값 저장
        next?.previous = prev   // 마지막 노드가 아닐 때
        if next == nil {        // 마지막 노드일 때
            tail = prev
        }
        
        // 연결 해제
        node.previous = nil
        node.next = nil
        
        return node.value
    }
}

let dogBreads = LinkedList<String>()
dogBreads.append(value: "Labrador")
dogBreads.append(value: "Bulldog")
dogBreads.append(value: "Beagle")
dogBreads.append(value: "Husky")

print(dogBreads)    //__lldb_expr_14.LinkedList

extension LinkedList: CustomStringConvertible {
    public var description: String {    //computed property
        var text = "["
        
        var node = head
        while node != nil {
            text += "\(node!.value)"
            node = node!.next
            if node != nil {
                text += ", "
            }
        }
        
        return text + "]"
    }
}
// [Labrador, Bulldog, Beagle, Husky]