단방향 연결리스트 - 선형구조

연결리스트는 배열과 많이 비교되고는 합니다. 

배열은 연속된 데이터의 나열입니다. 메모리상에 0 번부터 n 번까지 순차적으로 값이 할당되어 있으며 접근시 O(1) 의 시간복잡도를 가집니다. 단점으로는 값을 추가하거나 제거할때 추가한만큼 추가한 값 이후 또는 이전의 값이 순회하면서 순차적으로 밀려나야 하기때문에 O(n) 의 시간 복잡도를 갖습니다.

 

이와 반대로 단방향 연결리스트는 연속될수도 아닐수도 있습니다. 각 데이터들은 노드라고 부르며 이 노드들은 각자 다음 노드를 가르키고 있습니다. 때문에 연결리스트에서는 다음값을 알기위해서는 처음부터 순차적으로 접근해야합니다. 

 

이때 단방향이라고 부르는 이유는 이전노드가 다음 노드의 메모리정보만 갖고있기때문입니다. 단방향이 있으니 양방향 연결리스트도 있습니다. 이때 노드는 다음값의 메모리주소와 이전값의 메모리주소 모두 갖고있고 단방향 연결리스트보다는 좀더 효율적으로 찾으려는 값에 접근할 수 있습니다.

 

그러나 배열과는 다르게 값의 추가나 삭제를 할때는 O(1) 의 시간 복잡도를 갖습니다.

 

여기서는 이 단방향 연결리스트를 자바스크립트로 구현하는 과정을 정리하려고 합니다.

 

1단계 - Node 생성

첫번째로 노드를 만들어야합니다. 이 노드는 자기 자신의 값과 다음에 올 값을 알고 있어야합니다. 즉 2개의 프로퍼티를 가진 객체를 생성할 수 있어야 합니다.

 

 

 

2단계 - 기능을 정의할 메소드를 가진 객체

두번째로 노드를 활용하여 단방향 연결리스트의 기능을 구현할 객체를 만들어야 합니다.

연결리스트는 가장 첫번째값과 가장 마지막 값만 알고 있다면 언제든이 값을 추가하거나 제거하거나 값을 찾을 수 있습니다.

이 첫번째 노드를 head 가장 마지막 노드를 tail 이라고 하겠습니다.

 

 

3단계 - 기능구현 (addFirst)

이제 메서드 기능을 하나씩 구현하려고 합니다. 우선 가장 첫번째에 값을 추가하는 메소드를 정의하려고 합니다. 

이 메서드는 추가될때마다 해당 데이터는 가장 맨앞의 노드에 위치하게되고 기존에 있던 값은 추가된 노드의 바로 다음값으로 연결됩니다.

 

 

4단계 - 기능구현 (addLast)

이번엔 가장 마지막에 노드를 추가하는 메서드를 작성하려고 합니다. addLast 는 값을 전달받아 새로운 노드객체를 생성하고 _size 가 0이라면 해당 값이 가장 처음값이기 때문에 이땐 addFirst 를 호출합니다. 만약 값이 하나라도 있다면 현재 tail 의 next 에 새로 생성한 노드를 추가합니다. 그리고 tail 에 새로 생성한 노드를 할당합니다.

 

 

5단계 - 기능구현 (findNode)

findNode 는 특정 위치의 노드를 찾는 메소드입니다. 배열과 다르게 index 값으로 O(1) 로 접근할 수 없기때문에 이전 노드는 다음 노드를 알고있다는 특성을 활용하여 노드를 찾도록 해야합니다. 단방향 연결리스트에서는 다음 노드를 알기위해서는 이전 노드를 알아야하고 그렇다면 결국 head 를 알아야 원하는 노드를 찾을 수 있습니다. 

 

 

6단계 - 기능구현 (add)

add 는 index 와 value 두 매개변수를 받아 index 해당하는 위치에 value를 가진 노드를 생성하여 넣고 이전노드 또는 다음노드와 연결시켜야 합니다.

 

 

7단계 - 기능구현 (removeFirst)

첫번째 값을 제거하는 메서드를 구현합니다. 첫번째 값이 제거된다면 head.next 가 head 가 되면 됩니다.

 

 

8단계 - 기능구현 (removeLast)

마지막 값을 제거하는건 약간의 복잡도가 있습니다. 우선 tail 이 제거되면 tail 이전의 노드가 tail 이 되어야 하고 이 이전 노드의 next 에 연결되어있던 tail 의 값을 끊어줘야합니다. tail 이전의 노드를 구하기위해 이전에 만들었던 findNode 를 활용합니다.

 

 

9단계 - 기능구현 (remove)

remove 는 index 에 해당하는 노드를 찾아서 타켓 노드의 이전값의 next 에 다음 노드를 연결해주면됩니다.

 

10단계 - 기능구현 (toString)

해당 메소드는 현재 노드에 존재하고 있는 값들을 확인하기 위한 기능입니다.

 

 

여기까지 간단하게 단방향연결리스트를 자바스크립트를 활용하여 구현하는 예제를 진행해 보았습니다.

다음번엔 양방향 연결리스트를 자바스크립트로 구현하는예제를 진행해 보려고 합니다.