Linked List - 개념편

Linked List 란?

Linked List는 Array List 와는 달리, 요소와 요소 간의 연결(link)를 이용해서 구현한 리스트를 말한다.

Linked List에서 가장 중요한 것은 "연결"이 무엇인가를 파악하는 것이다.

메모리

컴퓨터에는 3가지 중요한 부품이 있는데, CPU, 메모리 스토리지이다.

메모리는 보통 RAM이라고 부르는데, Random Access Memory의 약자이다.

스토리지에는 HDD와 SDD같은 것들이 있다.

메모리는 속도가 매우 빠른 한편 용량이 작고, 전원이 꺼지면 데이터가 사라진다.

반면 스토리지는 속도가 느리기 때문에 CPU와 함께 작업을 처리하기에는 부족하다.

그래서 어떤 프로그램을 실행할 때, 프로그램과 데이터는 스토리지에서 메모리로 옮겨지고, CPU는 메모리에 로드된 데이터를 가지고 일을 처리하게 된다.

따라서 실행 속도를 결정하는 것은 대체로 메모리 이다.

🌟 우리가 자료구조를 배우는 이유는 메모리의 효율적인 사용을 위해서이다!

메모리의 구조

메모리는 건물로 비유할 수 있다. Array List와 Linked List는 각각 이 건물의 일부를 임대해서 사용하고 있는 회사라고 생각해보자.

• Array List 회사는 모든 직원이 한 층에 모여있어야 한다는 철학을 가지고 있다. 회사가 성장해서 사무실을 늘리고 싶어도, 바로 옆에 붙어있는 공간이 없기 때문에 현재 상황에서는 불가능하다. 더 큰 공간이 필요하다면 더 넓은 공간을 찾아 전체가 이사해야 한다. 배열이 이와 유사하다.
• Linked List 회사는 한 건물 내에 사무실들이 여기저기 떨어져 있다. 직원이 늘어나면 건물에서 비어 있는 곳 아무 곳이나 들어가면 된다. 그런데 사무실을 찾기는 조금 까다롭다. 방문자가 3번째 사무실을 찾아가기 위해서 먼저 첫 번째 사무실을 찾아간 다음, 다음 사무실의 위치를 물어보고, 그 사무실로 이동한 후에 다시 그 다음 사무실을 물어봐야 최종목적지에 도착할 수 있다. linked list 가 이와 유사하다.

Linked List vs Array List

	추가/삭제	인덱스 조회
Linked List	빠르다	느리다
Array List	느리다	빠르다

연결

배열과 달리, Linked List 는 그 위치가 이곳저곳으로 흩어져 있기 때문에 서로 연결되어 있어야 한다.

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

구조

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

각 노드가 다음 노드를 알고 있기 때문에 하나로 연결될 수 있다.

구현 방법은 여러가지이다.

객체지향 언어라면 객체에 데이터 필드와 링크 필드를 만든다. 보통 데이터 필드는 value 라는 이름의 변수, 링크 필드는 next 변수를 사용한다.

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

head

건물에 들어가려면 출입문을 찾아야 하듯, Linked List 의 입구에 해당하는 것이 head 이다. Linked List 를 사용하려면 head 가 가리키는 첫 번째 노드를 찾아야 한다.

데이터의 추가

아래의 그래픽은 visualgo.net 사이트를 이용했다. 알고리즘과 자료구조를 시각화해서 보여주는 서비스이다.

visualising data structures and algorithms through animation - VisuAlgo

---

1) 시작 부분에 추가

1. 새로운 노드를 생성한다.

Vertex vtx = Vertex(v)

2. 새 노드의 다음 노드로 첫번째 노드(head)를 가리킨다.

vtx.next = head 

3. 새 노드가 첫 번째 노드가 되도록 head의 값을 변경한다.

head = vtx

전체 코드

Vertex vtx = new Vertex(v)

vtx.next = head

head = vtx

2) 중간에 추가

1. 3번째 자리(인덱스 2)에 90을 추가할 것이다. 우선 3번째 자리를 찾아야 한다.
   

2. head를 참조해 첫번째 노드를 찾는다.

Vertex pre = head

3. 7의 자리에 새 노드를 위치시키려면 2(인덱스 1)를 알고 있어야 한다. 2의 next 로 새 노드를 지정해주어야 하기 때문이다. 2를 pre로 지정하기 위해 다음 반복문을 수행한다.

// i는 2 
for (k = 0; k < i-1; k++)
	pre = pre.next 

4. 2의 next를 이용해 77을 찾아 aft로 지정한다.

Vertex afr = pre.next 

5. 값이 80인 새 노드를 생성한다.

Vertex vtx = new Vertex(v)

6. 새 노드의 다음 노드로 77을 지정해준다.

vtx.next = aft

7. 2의 다음 노드로 새 노드(80)를 지정해 준다.

pre.next = vtx

8. 80이 3번째 자리에 오게 되었다.
   

전체 코드

Vertex pre = head
for (k = 0; k < i-1; k++)
	pre = pre.next
Vertex aft = pre.next
Vertex vtx = new Vertex(v)
vtx.next = aft
pre.next = vtx

데이터의 제거

세번째 노드(인덱스2)를 제거해 보자.

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

Vertex pre = head

2. 두 번째 노드(인덱스 1)로 이동한다.

for (k = 0; k < i-1; k++)
	  pre = pre.next

3. 두번째 노드에서 next를 이용해 세번째 노드(삭제 대상)를 찾고, 세번째 노드에서 next를 이용해 다음 노드를 찾는다.

Vertex del = pre.next, aft = del.next

4. 두 번째 노드의 다음 노드로 네 번째 노드(6)을 지정해 준다.

pre.next = aft

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

delete del 

전체 코드

if empty, do nothing
Vertex pre = head
for (k = 0; k < i-1; k++)
	  pre = pre.next
Vertex del = pre.next, aft = del.next
pre.next = aft // bypass del
delete del

배열의 경우 엘리먼트를 중간에 추가/삭제할 경우 해당 엘리먼트 뒤에 있는 모든 엘리먼트가 자리를 이동해야 한다. 그래서 배열은 추가/삭제가 느리다.
반대로 linked list는 추가/삭제될 엘리먼트의 전후 참조값만 변경하면 되기 때문에 추가, 삭제 속도가 빠르다.

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

linked list 에서 인덱스를 이용해서 데이터를 조회하려면 head가 가리키는 노드부터 시작해서 순차적으로 노드를 찾아가는 과정을 거쳐야 한다. 만약 찾고자 하는 요소가 가장 끝에 있다면 모든 노드를 거쳐야 한다. 건물 비유에서 n번째 사무실까지 가려면 물어물어 가야 했던 것을 생각해 보자.

반면 Array List 의 경우 인덱스를 이용해 특정 요소에 바로 접근할 수 있기 때문에 조회에 있어서는 매우 빠르다.

Linked List vs Array List

이처럼 각각의 자료구조는 장단점이 존재하고, 상황에 따라 적절한 자료구조를 선택하는 것이 중요하다.

	추가/삭제	인덱스 조회
Linked List	빠르다	느리다
Array List	느리다	빠르다

---

참고자료

Linked list - Data Structure (자료구조)