[자료구조] 연결 리스트 (단방향)

배열 VS 연결 리스트

리스트에 대해 본격적으로 들어가기 전에 배열과의 차이점에 대해서 알아보자.

연결 리스트 역시 이전에 포스팅 했던 배열과 마찬가지로 데이터를 표현하는 자료구조 중 하나이다.

 

*배열과 연결 리스트는 서로의 장단점을 보완하고 있다.

 

배열

배열은 인덱스를 이용해서 하나의 메모리 공간 안에 데이터들이 나란히 저장되어 있다.

그래서 인덱스를 통해 데이터에 접근할 수 있고 인덱스만 알고 있다면 값에 대한 접근이 매우 빠르다.

 

그러나, 처음이나 마지막 인덱스가 아닌 요소를 추가/삭제한다면 element(index+value)를 재배치하는 작업 때문에 오버 헤드가 발생할 수 있다는 단점이 있다.

 

 

연결 리스트

연결 리스트는 배열의 단점을 보완한 것이다.

따라서 배열과 같이 순차적으로 데이터를 보관하는 것이 아니라 각각 떨어진 공간에 존재하는 데이터를 연결한 것이다. 

 

🟢 장점 

그러므로 메모리에 공간을 할당해서 element를 저장하면 되고,

배열처럼 중간의 element를 추가/삭제할 때 재배치 시 발생하는 오버헤드도 나타나지 않는다.

(연결만 새로 바꿔주면 되기 때문이다.)

 

🔴 단점 

그러나 배열처럼 인덱스로 접근한 것이 아니기 때문에

데이터에 접근하기 위해서는 첫번째 데이터부터 원하는 데이터까지 순차적으로 찾아가서 원하는 데이터인지 찾아야 한다. (단방향 연결리스트의 경우) 최악의 경우에는 n개의 데이터에 대해 n번 찾아야 한다. 

또한, 현재 데이터에서 다음 데이터에 대한 연결 정보를 별도의 데이터 공간에 저장해야 하므로 저장 공간의 효율이 높지 않다.

 

 

	배열	연결 리스트
장점	- 인덱스 값을 알고 있다면 데이터에 빠르게 접근할 수 있다. - 새로운 요소의 삽입이 빠르다.	- 데이터의 추가/삭제가 빠르다.
단점	- 크기가 고정되어 있다. - 삭제/검색이 느리다.	- 검색 속도가 느리다. - 저장공간의 효율이 높지 않다.

 

---

단방향 연결 리스트

연결 리스트는? 연속되지 않은 메모리에 저장된 데이터들을 연결시켜 놓은 것이다. 

이 때 연결은, 내 다음 순서의 주소 값을 내가 갖고 있어야 한다. 그래야 현재 데이터에서 다음 데이터로 연결할 수 있다.

 

data

next

 

단방향 연결 리스트의 경우 데이터 모양이 위와 같다.

data는 현재 데이터(= 내 데이터)를 저장하는 것이고

next는 내 다음 데이터의 주소값을 저장하는 것이다.

 

이런 형태를 노드라고 부른다.

그리고 연결 리스트는 이런 노드들이 연결되어 이루어진 자료구조라고 말한다.

 

구현

1. 노드 생성

class Node<T> {
    var data: T?
    var next: Node?
    
    init(data: T?, next: Node? = nil) {
        self.data = data
        self.next = next
    }
}

그리고 단방향 연결 리스트 속성에 맞게 새로운 element가 추가될 때 Node를 하나 생성해서 연결하면 된다.

 

 

2. 연결 리스트 생성

2-1. 헤드 생성

단방향 연결 리스트의 경우 해당 리스트의 가장 첫번째 노드인 헤드가 존재한다.

class LinkedList<T> {
    private var head: Node<T>?
}

 

 

2-2. append(data:) : 연결 리스트 맨 마지막에 노드 추가하기

연결 리스트에 새로운 요소를 삽입하는 경우, 가장 마지막 노드를 찾아서 그 뒤에 추가하면 된다.

가장 마지막 노드를 찾는 방법은 head 노드부터 순회해서 node.next가 nil인 경우를 찾아서 삽입하고자 하는 노드와 연결하면 된다.

class LinkedList<T> {
    private var head: Node<T>?
    
    func append(data: T?) {
        // head가 없는 경우
        if head == nil {
            head = Node(data: data)
            return
        }
        
        // head가 있는 경우
        var node = head
        // head.next가 nil일 때까지 순회
        while node?.next != nil {
            node = node?.next
        }
        // nil인 노드를 찾아, 그 뒤로 노드를 생성 및 연결
        node?.next = Node(data: data)
    }
}

 

 

2-3. insert(data:at:) : 연결 리스트 중간에 노드 추가하기

연결 리스트의 경우 중간에 노드를 추가할 수 있다. 

이 때 배열과 다르게 인덱스가 없기 때문에 중간의 노드 간 연결을 바꿔주면 된다.

 

연결하고자 하는 범위의 바로 앞까지 순회해서 그 뒤의 노드를 추가하고자 하는 노드로 연결하고 추가한 노드의 next에 앞서 이전과 연결되어 있던 노드를 연결한다.

 

    func insert(data: T?, at index: Int) {
        
        //head가 없는 경우 Node를 생성 후 head로 지정한다
        if head == nil {
            head = Node(data: data)
            return
        }
        
        var node = head
        for _ in 0..<(index - 1) {
            if node?.next == nil { break }
            node = node?.next
        }
        
        let nextNode = node?.next
        node?.next = Node(data: data)
        node?.next?.next = nextNode
    }

 

 

2-4. removeLast : 연결 리스트 맨 마지막 노드 삭제하기

먼저 마지막 노드를 찾아서 그 앞의 노드에서 next를 nil로 바꾸면 된다.

    func removeLast() {
        
        if head == nil { return }
        
        // head를 삭제하는 경우
        if head?.next == nil {
            head = nil
            return
        }
        
        var node = head
        while node?.next?.next != nil {
            node = node?.next
        }
        
        node?.next = node?.next?.next
    }

 

 

2-5. remove(at:) 연결 리스트 중간 노드 삭제하기

삭제할 노드의 바로 이전 노드의 next를 삭제할 노드의 next로 바꿔주면 된다.

    func remove(at index: Int) {
        
        if head == nil { return }
        
        // head를 삭제하는 경우
        if index == 0 || head?.next == nil {
            head = head?.next
            return
        }
        
        var node = head
        for _ in 0..<(index - 1) {
            if node?.next?.next == nil { break }
            node = node?.next
        }
        
        node?.next = node?.next?.next
    }

 

 

2-6. searchNode(from:) data로 노드 찾기 

노드에 저장된 데이터를 검색해서 해당 노드를 반환하려면, head부터 순차적으로 돌면서 찾으면 된다.

 

while node?.next != nil {
    if node?.data == data { break; }
    node = node?.next
}

이 때, 위와 같은 반복문을 돌 수 있는데 이렇게 코드를 작성하면 오류가 난다.

 

찾고자 하는 데이터의 형태와 노드의 데이터의 형태가 모두 제너릭으로 선언이 되어 있기 때문에 자료형을 런타임 전까지 모르기 때문이다.

그래서 ==을 사용할 수 있는 Equatable 프로토콜이 채택된 자료형인지 아닌지 모르기 때문에 위와 같은 오류가 발생한다.

 

그러므로 이를 해결하기 위해서는 (우리는 데이터를 비교를 해야하기 때문에)

LinkedList 클래스에 해당 프로토콜을 채택하면 된다.

 

---

단방향 연결 리스트의 가장 큰 단점은 바로 탐색이다.

 

만약 n개의 노드가 있을 때 하나의 특정 노드를 찾고 싶다면/새로운 노드를 추가하고 싶다면, head에서부터 마지막 n번째 노드까지 매번 순차적으로 탐색해야한다. 

 

이러한 단방향 연결 리스트의 단점을 보완한 자료구조가 양방향 연결 리스트이다.

 

head

nil

3

중간 노드 

4

tail 

7

nil

 

앞서 단방향 연결 리스트의 경우, 데이터와 다음 노드의 주소값을 갖고 있었다면,

양방향 연결 리스트의 경우 어디와 연결되어 있는지/가장 첫 노드를 가르키는 head/가장 마지막 노드를 가르키는 tail도 갖고 있기 때문에 양방향으로 접근할 수 있다.