[ 자료구조] 단일 연결 리스트 - Add 구현하기[1]. sub | 노드를 앞으로 추가해보자

단일 연결 리스트란?

단일 연결 리스트는 리스트의 각 요소가 다음 요소를 가리키는 연결 리스트의 한 유형이다. 리스트는 노드를 요소로 가지고 있으며, 각 노드에는 데이터(data)와 다음 노드를 가리키는 참조(next) 를 담고 있다.

 

리스트에서 첫 번째 노드를 헤드(head)라 부르며, 마지막 노드는 null 에 대한 참조 담는다. 마지막 노드가 null 을 담고 있는 것은 [1 -> 2 -> 3] 이 있을 때 3을 담고 있는 노드의 다음 노드는 없기 때문이다.

 

단일 연결 리스트는 단방향 이므로 이전 노드에 대한 참조를 알지 못하는 것이 특징이다. 즉, 앞만 보거나, 뒤만 보거나 둘 중 하나의 방향만 가리킨다.

 

단일 연결 리스트의 시간 복잡도

단일 연결 리스트는 특정 위치의 노드에 직접 접근하려면 처음부터 해당 위치까지 순차적으로 접근해야 하므로 시간 복잡도가 O(n)이 된다. 이는 결국 단방향 특성으로 인해 어떠한 경우에도 순서를 뛰어 넘지 못하기 때문이다.  즉, 노드를 추가, 삭제, 검색 하는 모든 동작이 선형적으로 연산 횟수가 증가하므로 O(n) 이 된다. 

 

참고로, 메모리 상의 공간에 연속적으로 배치되는 배열의 경우 O(1) 시간 복잡도를 가진다.그 이유는  해당 위치에 해당하는 인덱스를 사용하여 아무리 배열의 크기가 크더라도 전체 순회 필요 없이 바로 접근할 수 있기 때문이다.

 

단일 연결 리스트에서 Node의 구성

보통 Node 를 구현할 때 class 를 사용하므로 Node 클래스라고 명명지어서 설명해본다면, Node 클래스는 data 와 next 라는 두 가지 프로퍼티를 가지고 있다.

 

data 는 리스트에 추가되는 값(혹은 각각의 노드가 담고 있는 값)을 의미하며, next 는 현재  노드에서 다음 순서로 추가되는 노드에 대한 참조(쉽게 말해 링크나 화살표를 의미)를 저장하고 있다(사실 노드를 어떤 방향으로 추가하느냐에 따라서 참조를 형성하는 방향은 차이가 있을 수 있다).

 

이를 자바스크립트 클래스로 구현하면 다음과 같은 형태가 된다.

class Node {
	constructor(data) {
    	this.data = data; // 노드에 저장되는 데이터
        this.next = null; // 현재 노드의 다음 노드를 가리키는 화살표(참조)
    }
}

 

단일 연결 리스트의 List 클래스

앞서 살펴본 Node 를 담고 있는 클래스를 List 클래스 라고 한다.  완전히 같지 않지만 이해를 위해서 예를 들자면, [노드 → 노드 → 노드] 이런 형태로 노드를 감싸고 있다고 보면 된다.

 

List 클래스는 노드를 담고 있기 때문에, 노드에 대한 정보를 가지고 있다(Node 클래스의 인스턴스와 리스트의 길이 정보). 또한 아무런 노드를 가지고 있지 않은 경우에는 null 을 참조하고 있기 때문에 이를 자바스크립트 클래스 문법으로 나타내면 다음과 같은 형태가 된다.

class List {
	constructor() {
    	this.head = null
        this.size = 0
    }
}

 

Add 함수 구현하기 |  노드를 앞으로 추가

단일 연결 리스트에서 Add 함수를 구현하는 방법은 다양하다. 그 중에서도 제일 간단한 방식은 노드를 앞으로 추가해 나가는 방식이다. 이를 코드로 구현해보면 다음과 같다.

  add(data) {
    const newNode = new Node(data) // 1. 새로운 노드를 생성한다(Node 클래스 인스턴스 생성).
    
    newNode.next = this.head // 2. 추가된 노드의 다음 노드는 현재 노드를 참조
    this.head = newNode // 3. 현재 노드의 자리에는 추가된 노드를 할당한다.
    this.size++ // 4. 새로운 노드가 추가되었으므로 리스트의 크기를 증가시킨다.
 }

 

완성 후 add 함수를 호출하고 값을 추가 시켜 보자

const list = new List

list.add(1)  
list.add(2)  
list.add(3)  
list.add(4)  

console.log(list)
console.log(list.size) // 4

 

 

특이하게도 값이 추가된 순서대로 참조를 가리키는 것이 아니라 이전 참조를 화살표(next)가 가리키는 것을 볼 수 있다.

 

아래 코드를 다시 살펴보자. 이 포스트를 시작하기 처음에 단일 연결 리스트의 정의 부분을 설명할 때, 첫 번째 노드를 헤드라고 했는데, 새로운 노드의 다음 노드를 현재 노드로 지정하고, 현재노드의 자리에는 새로운 노드를 지정함으로써, 매번 새롭게 추가되는 노드를 헤드(즉, 첫 번째 노드)로 지정하기 때문에 아까와 같은 결과가 나타난 것이다.

- 현재 노드에 1이 들어 있고, 새 노드에 2가 들어 있다면, 새 노드(2) 가 가리키는 다음 노드(next) 에는 현재 노드(1) 를 저장 - 현재 노드(1) 의 자리에는 새 노드(2) 를 할당함으로써 새노드를 헤드(첫 번째 자리의 노드)로 지정

    newNode.next = this.head // 2. 추가된 노드의 다음 노드는 현재 노드를 참조
    this.head = newNode // 3. 현재 노드의 자리에는 추가된 노드를 할당한다.

 

즉, 1 , 2 , 3, 4  를 순서대로 add 함수를 통해 노드에 추가했지만,  매번 추가되는 값마다 1 → 2 →  3 → 4 → newNode  의 순서로 헤드를 새롭게 지정하기 때문에, 결과적으로  4의 다음 노드는 3, 3의 다음 노드는 2 를 가리키는 형태가 된다.

1 을 추가했을 때  1 2 를 추가했을 떄  2 ▶ 1 3 을 추가했을 떄  3 ▶ 2 ▶ 1 4 를 추가했을 떄  4 ▶ 3▶2▶1

 

 

 

 

[자료구조] 단일 연결 리스트 | Add 구현하기(2). sub | 뒤로 노드 추가하기