[자료구조] 연결리스트-2 (추가/삭제)

2021.07.12 - [자료구조] - [자료구조] 연결 리스트-1 에 이은 내용

 

앞선 포스팅에서 노드를 구성했다면

이번 포스팅에선 노드를 관리하고 추가/삭제가 용이한 연결리스트 클래스를 만들것이다.

 

이전 포스팅에서 작성한 노드 클래스

노드클래스가 준비되었으니 바로 시작하자.

---

LinkedList클래스를 생성하면 head라는 속성을 추가해준다. 변수명은 조금 달라도 되지만 보통 첫번째 노드를 가리키는 명칭이면 된다.

head에는 LinkedList의 첫번째(0번째) 노드를 할당하자.

 

1. Append

class LinkedList {
    var head: Node?
    
    func append(value: Int) {
        let newNode = Node(data: value)
        if head == nil {
            head = newNode
        } else {
            var current = head
            while current?.nextAddress != nil {
                current = current?.nextAddress
            }
            current?.nextAddress = newNode
        }
    }
    
    //마지막 데이터를 출력하는 메서드를 추가해봤다.
    func printLast() {
        if head != nil {
            var current = head
            while current?.nextAddress != nil {
                current = current?.nextAddress
            }
            
            print(current?.data)
        }
    }
}

let linkedList = LinkedList()
linkedList.append(value: 0)
linkedList.append(value: 1)
linkedList.append(value: 2)
linkedList.printLast()

append메서드는 LinkedList에 노드를 하나씩 이어붙이는 기능을 한다.

만약 LinkedList에 노드가 전혀 없는 상태라면 head를 해당 노드로 할당하고, 이미 있는경우 head.nextAddress...를 반복하여 

마지막 노드를 찾아낸다. 그 다음 마지막 노드의 nextAddress를 새로운노드로 할당해준다.

 

append는 단순하게도 LinkedList의 마지막 노드에 이어붙이는 기능만 제공한다.

위에서는 0,1,2 순서로 노드를 연결시켜줬는데, 0을 append할 때 LinkedList의 head는 0을 데이터로 가진 노드로 할당된다.

위 코드의 출력결과는 2가 나온다.

 

 

2. Remove

remove 메서드는 맨마지막 요소를 삭제한다. 

func removeLast() {
	if head?.nextAddress == nil {
    	head = nil
    } else {
    	var current = head
        var nextNode = current?.nextAddress
        while nextNode?.nextAddress != nil {
            current = nextNode
            nextNode = nextNode?.nextAddress
        }
        current?.nextAddress = nil
    }
}

만약 head가 비어있거나 head의 nextAddress가 없는상태라면 head를 nil로 초기화 한다.

그게 아니라면 append메서드와 비슷하게 nextAddress가 nil인 노드를 찾아서 순차탐색을 진행하는데

이때 중요한건 nextAddress가 nil인 노드를 삭제하는게 아니라 , 이 노드를 nextAddress로 갖고 있는 바로 이전 노드의 nextAddress값을 nil로 처리하는것이다.

그러면 자연스레 마지막 노드를 연결하는 링크가 해제되었으므로 결과적으로는 맨 마지막 노드가 삭제된것과 같은 모습이 된다.

 

그림으로 이해

1-2-3 연결중

2와 3의 링크를 끊는다.

1과 2가 남고 2의 nextAddress가 nil이기 때문에 마지막 노드로 판단한다.

 

다음글 :

2021.07.14 - [분류 전체보기] - [자료구조] 연결리스트-3 (양방향 연결 리스트)

 

최종 코드

import UIKit

class Node {
    var data: Int?
    var nextAddress: Node?
    init(data: Int) {
        self.data = data
    }
    
    func setNextNode(_ next: Node) {
        nextAddress = next
    }
    
    func printData() {
        print(data ?? "data is nil")
    }
}

class LinkedList {
    var head: Node?
    
    func append(value: Int) {
        let newNode = Node(data: value)
        if head == nil {
            head = newNode
        } else {
            var current = head
            while current?.nextAddress != nil {
                current = current?.nextAddress
            }
            current?.nextAddress = newNode
        }
    }
    
    func removeLast() {
        if head?.nextAddress == nil {
            head = nil
        } else {
            var current = head
            var nextNode = current?.nextAddress
            while nextNode?.nextAddress != nil {
                current = nextNode
                nextNode = nextNode?.nextAddress
            }
            current?.nextAddress = nil
        }
    }
    
    //마지막 데이터를 출력하는 메서드를 추가해봤다.
    func printLast() {
        if head != nil {
            var current = head
            while current?.nextAddress != nil {
                current = current?.nextAddress
            }
            
            print(current?.data)
        } else {
            print("head is nil")
        }
    }
}

let linkedList = LinkedList()
linkedList.append(value: 0)
linkedList.append(value: 1)
linkedList.append(value: 2)
linkedList.append(value: 3)
linkedList.append(value: 4)
linkedList.printLast() //4
linkedList.removeLast()
linkedList.printLast() //3
linkedList.removeLast()
linkedList.printLast() //2
linkedList.removeLast()
linkedList.printLast() //1
linkedList.removeLast()
linkedList.printLast() //0
linkedList.removeLast()
linkedList.printLast() //head is nil