[자료구조] 연결 리스트-1

자료구조의 리스트는 순차리스트(배열)과 연결리스트(Linked List)로 나뉜다.

 

연결리스트는 순차리스트와 달리 삽입/삭제 등 변화에 더욱 편리한 자료구조인데, 이러한 강점은 연결리스트의 각 요소가 어떻게 구성되는지 알면 이해가 된다.

 

연결리스트의 각 요소를 Node(이하 노드)라고 하는데, 노드는 정보를 담는 데이터와 연결된 다른 노드의 주소(포인터)를 담는다. 그림으로 표현한다면 아래와 같다.

 

Data와 Next Address를 묶어서 하나의 노드라고 한다. Next Address는 위에서 말한 다음 노드의 주소를 담고있다.

언어에 따라서 NextAddress에 타입은 적절한 형태로 바뀔 수 있겠지만 보통의 경우 NextAddress에 할당되는것은 다음으로 연결되어야 할 노드의 주소가 된다.

 

 

노드 만들기

만약 숫자 1을 노드로 만들고 싶다면 Data와 NextAddress를 포함한 Class를 만든다.

Class는 참조타입이므로 NextAddress = Node() 와 같이 작성만 하면 다음으로 연결 될 노드의 주소가 할당된다.

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")
    }
}

Node를 생성하면서 data를 1로 초기화 시켜줬다. NextAddress는 아직 할당되지 않았기 때문에 빈 상태이다. 

그리고 printData()를 호출해서 first노드가 가진 data를 확인해보면 콘솔창에 숫자 1이 정상적으로 찍히는것을 볼 수 있다.

first의 상태

이제 NextAddress에 다른 노드들을 연결해보자.

 

 

 

 

노드 연결하기

일단 하나의 노드가 만들어졌다. 연결하려면 두개 이상의 노드가 준비되어야한다. 숫자 2, 숫자 3의 데이터를 노드로 만들어서 연결해보자.

위에서 first노드를 만든것처럼 2와 3도 똑같이 노드로 만들어준다.

두개의 노드를 추가로 만들었다. 

second를 first의 next로 연결하고 second의 next는 third가 되게 하자.

 

노드클래스에 다음 노드를 연결해주는 메서드가 이미 구현되어 있다.

next로 들어오는 노드를 현재 노드의 nextAddress에 할당한다. 

그렇다면 first.setNextNode(second)  second.nextNode(third)를 사용해서 1-2-3 노드를 연결해 준다.

 

 

정상적으로 데이터가 찍힌다.

first.nextAddress는 곧 second를 말하는것과 같다. 

first.nextAddress가 second이므로 first.nextAddress.nextAddress는 third다.

 

---

자, 연결리스트의 노드에 대해서 알아보고 연결하는 것까지 해봤다. 하지만 추가해야할 노드가 있을 때 마다 setNextNode를 호출해서 하나하나 연결해주고 있는 미완성의 모습이다.

연결리스트의 원리를 알았으니, 실제 구현은 다음 포스팅에서 알아보자.

 

다음글 :

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