Linked List (feat. Array List)에 대해서

소개

Linked List는 Array List와 다르게 엘리먼트와 엘리먼트 간의 연결(Link)을 이용해서 리스트를 구현한 것을 의미한다.

그렇다면 연결은 무엇이고 연결이 아닌 것은 무엇인지 생각해볼 필요가 있다.

 

메모리의 구조

일단 메모리의 구조에 대해서 먼저 알아보겠다.

Array List와 Linked List라는 두 회사가 건물의 일부를 임대해서 사용한다고 생각해보자.

Array List 회사

이 회사는 모든 직원이 한 곳에 모여있어야 한다는 철학이 있기 때문에 사무실이 모여있다.

만약 회사가 성장해서 사무실이 좁아지면 더 이상 새로운 직원을 뽑을 수 없다.

또한 만약 더 많은 공간이 필요하다면 더 많은 사람을 수용할 수 있는 공간을 찾아 전체가 이사를 해야 한다.

 

Array List는 위의 비유처럼 메모리를 사용한다.

Linked list 회사

이 회사는 한 건물 내에서 한 회사가 임대한 사무실이 서로 떨어져 있다.

덕분에 직원이 늘어도 건물의 비어있는 곳 아무 데나 임대해서 들어가면 된다.

 

하지만 방문자가 사무실을 찾아가는 방법이 비효율적이다.

3번째 사무실을 찾아가려면 1번째 사무실에 가서 2번째 사무실의 위치를 물어보고 찾아가야 한다.

2번째 사무실에서 3번째 사무실의 위치를 알려주어야 비로소 3번 째 사무실을 찾아갈 수 있다.

 

이렇게 물어물어 사무실을 찾아가야 하는 방식이 Linked list이다.

반면에 Array list는 엘리먼트가 같은 곳에 모여있기 때문에 3번째 사무실에 한 번에 찾아갈 수 있다.

연결

비유를 통해 알아보았듯이 Linked list는 그 위치가 흩어져 있기 때문에 서로 연결되어야 한다.

Linked list는 다양한 자료 구조에서 광범위하게 사용되는 개념이기 때문에 잘 이해할 필요가 있다.

 

용어 정리를 해보자.

Array list는 엘리먼트라는 이름을 사용했지만,

Linked list와 같이 연결된 엘리먼트는 노드(node) 혹은 버텍스(vertex)라고 부른다.

 

이러한 용어들은 연결성이 강조된 표현이라고 할 수 있다.

구조

Linked list의 구조를 알아보자.

리스트는 노드들의 모임이다. 따라서 내부적으로 노드를 가지고 있어야 한다.

Array list의 경우 엘리먼트가 배열의 엘리먼트이다. Linked list는 배열 대신에 다른 구조를 사용한다.

 

노드는 최소한 두 가지 정보를 알고 있어야 한다. 노드의 값은 다음 노드이다.

각각의 노드가 다음 노드를 알고 있기 때문에 하나의 연결된 값의 모임을 만들 수 있는 것이다.

Linked list의 구조

자바스크립트와 같은 객체지향 언어라면 객체에 데이터 필드와 링크 필드를 만든다.

보통 데이터 필드는 value라는 이름의 변수, 링크 필드는 next 변수를 사용한다.

value에는 노드의 값이 저장되고, next에는 다음 노드의 포인터나 참조값을 저장해서 노드와 노드를 연결시키는 방법을 사용한다.

 

Head

위의 Linked list 구조 그림을 보면 head라는 것이 있다.

다시 건물을 비유해보자. 건물에 들어갈 때는 출입문을 찾아야 한다.

 

리스트를 하나의 건물로 비유하자면 출입문에 해당하는 것이 head이다.

Linked list를 사용하기 위해서는 이 head가 가리키는 첫 번째 노드를 찾아야 한다.

데이터의 추가

내가 참고한 글에서 사용한 언어는 자바여서 예시 코드 또한 자바라는 점 참고 바란다.

후에 자바스크립트로 구현해보고 포스팅을 따로 할 예정이다.

시작 부분에 추가

노드를 첫 번째 위치에 추가해보자.

우선 새로운 노드를 생성한다.

Vertex temp = new Vertex(input)

새로운 노드의 다음 노드로 첫 번째 노드를 가리킨다.

temp.next = head

새로 만들어진 노드가 첫 번째 노드가 되도록 head의 값을 변경한다.

head = temp

전체 코드

Vertex temp = new Vertex(input)
temp.next = head
head = temp

중간에 추가

3번째 자리에 90을 추가해보자.

6과 23 사이에 90을 위치시키는 것이 목적이므로, 우선 3번 째 자리를 찾아야 한다.

head를 참조해서 첫 번째 노드를 찾았다.

Vertex temp1 = head

23의 자리에 새로운 노드를 위치시키기 위해서는 6을 알고 있어야 한다.

6의 next로 새로운 노드를 지정해야 하기 때문이다.

 

아래 코드는 6을 temp1으로 지정하기 위한 반복문이다.

//현재 k의 값은 2
while (--k!=0)
  temp1 = temp1.next

6의 next를 이용해서 23을 찾아 temp2로 지정한다.

Vertex temp2 = temp1.next

값이 90인 노드를 생성한다.

Vertex newVertex = new Vertex(input)

6의 다음 노드로 새로운 노드를 지정한다.

temp1.next = newVertex

새로운 노드의 다음 노드로 23번을 지정한다.

newVertex.next = temp2

이렇게 해서 90을 3번째 자리에 위치시켰다.

 

전체 코드

Vertex temp1 = head

while (--k!=0)
  temp1 = temp1.next
  
Vertex temp2 = temp1.next
Vertex newVertex = new Vertex(input)
temp1.next = newVertex
newVertex.next = temp2

데이터의 제거

데이터를 제거하는 것도 추가하는 것과 비슷하다.

세 번째 노드를 제거해보자.

우선 head를 이용해서 첫 번째 노드를 찾는다.

Vertex cur = head

두 번째 노드로 이동한다.

//k = 2
while (--k!=0)
  cur = cur.next

세 번째 노드를 찾았다.

Vertex tobedeleted = cur.next

두 번째 노드의 next를 23으로 변경한다. 그 후에 90을 제거한다.

cur.next = cur.next.next

90을 삭제해서 메모리에서 제거한다.

delete tobedeleted

 

전체 코드

Vertex cur = head

while (--k!=0)
  cur = cur.next
  
Vertex tobedeleted = cur.next
cur.next = cur.next.next
delete tobedeleted

인덱스를 이용한 데이터 조회

인덱스를 이용해서 데이터를 조회할 때 Linked list는 head가 가리키는 노드부터 시작해서 순차적으로 노드를 찾아가는 과정을 거쳐야 한다. 만약 찾고자 하는 엘리먼트가 가장 끝에 있다면 모든 노드를 탐색해야 한다.

 

반면에 array를 이용해서 리스트를 구현하면 인덱스를 이용해서 해당 엘리먼트에 바로 접근할 수 있기 때문에 매우 빠르다.

trade off

트레이드오프는 어떤 특성이 좋아지면 다른 특성이 나빠지는 상황을 의미한다.

Array list와 Linked list는 트레이드오프의 좋은 사례라고 할 수 있다.

 

자료 구조를 배우면 이러한 트레이드오프를 이해하고 각 상황에 맞는 올바른 선택을 하는 데에 큰 도움이 될 것 같다.

 

 

출처

https://www.opentutorials.org/module/1335/8821

Linked list - Data Structure (자료구조)