[자료구조] 1-2. 연결 리스트(Linked List)

연결 리스트는 순차 리스트와는 다르게, 리스트의 노드(요소)값의 메모리주소가 순차적이지 않다.

 

대신, 노드에 자신의 값과, 다음 노드의 메모리주소를 저장한다.

 

시작하는 노드를 머리(head)라고 하고, 맨 끝을 꼬리(tail)이라고 한다.

노드에서 다음 노드로 향하는 주소값을 포인터((Pointer)라고 한다.

tail노드에서 가지고 있는 포인터값은 none 또는 null이라 한다.

접근

[2]에 있는 값을 보려면, 머리부터 다음 노드를 하나하나 찾아가야한다.(순차적으로 탐색해야한다)

시간복잡도는 O(N)이다.

 

삽입

A - B - C로 연결되어있는 연결 리스트 중 B-C 사이에 D 노드를 삽입하고 싶으면, B의 포인터를 D의 메모리주소,

D의 포인터를 C의 메모리주소로 바꿔주면된다. 이때, 바꾸는 것의 시간복잡도는 O(1)이다. 

그러나, 바꾸려는 위치까지 가서(접근해서) 값을 바꿔주어야 하므로, 사실상 시간복잡도는 O(N)이다.

머리 노드에 삽입할 때에는 뒤까지 접근할 필요가 없다.

 

삭제

A - B - C로 연결되어있는 연결 리스트 중 B노드를 없애고싶으면, B의 포인터를 없애고, A의 포인터를 C의 메모리주소로 설정해주면 된다. 추가와 같이, 바꾸는 것의 시간복잡도는 O(1)이나, 바꾸려는 위치까지 접근해야 하므로 사실상 O(N)이다.

머리 노드를 삭제할 때에는 뒤까지 접근할 필요가 없으니 O(1)이다.

 

 순차리스트 VS 연결리스트

	순차 리스트(데이터 주소 정형화)	연결 리스트(데이터 주소 비정형화)
데이터에 접근	빠름(시작 메모리주소에서 인덱스만큼 점프)	느림(순차 탐색으로 목표 노드까지 가야함)
추가(삽입)/삭제	느림(다른 데이터들을 다 밀어내야함)	빠름(메모리 주소변경으로 끝) 단, 노드에 접근을 하고 변경