Linked List - 링크 리스트

어떤 언어이든 코딩의 기초를 배웠다면 array, 배열에 대해서 알 것이다.

하지만 Linked List는 학교에서 공부하지 않았다면 생소할 수도 있겠다.

 

Linked List는 배열과 사용 방법은 비슷하지만 구조적으로 다르게 작동한다.

 

제일 쉽게 풀어본다면 배열과 linked list가 메모리를 어떻게 사용하는가 를 볼 수 있겠다.

 

배열은, 이미 알고 있듯이, 메모리를 연속적으로 차지한다.

예를 들어 배열의 인덱스 0의 메모리 주소가 0x01이라고 치자. 그리고 배열의 크기는 4, 즉 4개의 값을 가지고 있다.

이 배열을 메모리에 저장하려면 메모리에 5개의 공간이 끊기지 않고 연속적으로 존재해야 한다.

다시 말해서 메모리 주소 0x01부터 0x04 가 이 배열에 사용된다.

메모리상 배열의 모습

만약, 그럴 일은 없겠지만, 메모리에 배열을 저장할 수 있는 공간이 없다면?

잘은 모르지만, 배열을 메모리에 저장할 때 컴퓨터는 그 공간이 있는지 확인, 확보, 그리고 저장한다.

확보 과정에서 필요하면 이미 저장된 데이터들을 다른 곳(메모리 주소)으로 옮겨서 공간을 확보한다.

만약 이 과정에서 필요한 공간을 확보하지 못했다면 메모리 부족 에러가 생긴다.

 

하지만 linked list는 이런 시스템적 부담감이 없다.

Linked List는 node를 만들어 데이터를 저장하고 이 node들을 pointer로 서로 연결한다.

node에는 value와 next 변수가 있다.

value 변수는 말 그대로 값을 저장하고, next 변수는 다음 node의 위치, 즉 메모리 주소를 저장한다.

처음에 있는 node를 head node라고 하고 맨 마직막에 있는 node를 tail node라고 한다.

 

아래 이미지에서 볼 수 있듯이 하나의 node를 저장할 수 있는 공간이 있으면 linked list를 만드는 게 가능한 거다.

메모리상 Linked List의 모습

뭐, 메모리 부족 에러는 피할 수 없지만....

 

 

Linked List엔 2 종류가 있다.

첫 번째는 Singly Linked List, 싱글 링크 리스트

두 번째는 Doubly Linked List, 더블 링크 리스트

 

이 둘의 차이점은 순회에서 제일 잘 볼 수 있다.

 

싱글 링크 리스트는 next pointer를 사용해서 앞으로만 갈 수 있다.

하지만, 더블 링크 리스트는 next와 previous pointer를 가지고 있어 앞/뒤로 자유롭게 순회할 수 있다.

 

더블 링크 리스트

 

 

그럼 구조적 차이 말고 배열과 링크 리스트엔 다른 어떤 차이점이 있나?

CRUD 작업에서 time complexity에 조금 차이가 있다.

 

Create: 새로운 값 넣기

	배열	링크 리스트
끝에 넣기	O(1)	O(1)
처음에 넣기	O(n)	O(1)
n번째에 넣기	O(n)	O(n)

Read: 값 가져오기

	배열	링크 리스트
끝에서 가져오기	O(1)	O(1)
처음에서 가져오기	O(1)	O(1)
n번째에서 가져오기	O(1)	O(n)

Update: 값 바꾸기

	배열	링크 리스트
끝의 값 바꾸기	O(1)	O(1)
처음의 값 바꾸기	O(1)	O(1)
n번째의 값 바꾸기	O(1)	O(n)

Delete: 값 지우기

	배열	링크 리스트
끝의 값 지우기	O(1)	O(1)
처음의 값 지우기	O(1)	O(1)
n번째의 값 지우기	O(n)	O(1) **n번째 까지 가는데는 O(n) 이지만 지우는 작업은 O(1) 이다**

 

 

 

혹시 틀린 정보가 있다면 알려주세요. 수정하겠습니다.