[자료구조] Linked List(연결 리스트) 란?

Linked List

Array의 메모리를 효율적으로 쓰기 위한 자료구조

 

① 데이터의 내용을 담는 부분과 ② 다음 노드의 주소값을 갖는 포인터 변수로 구성되어 있다.

리스트의 첫번째 노드를 헤드(Head) 마지막 노드를 테일(Tail)이라고 한다.

 

Linked List는 메모리상에서 연속적이지 않지만, 각각의 원소가 다음 메모리 주소값을 저장하고 있기 때문에 논리적인 관점에서는 연속적이라고 볼 수 있다.

tree, graph등 다른 자료구조를 구현할 때 자주 쓰이는 기본 자료구조이다.

 

 

중간 인덱스의 데이터 삽입, 삭제

Array의 경우는 데이터를 전부 한칸씩 밀어줘야 해서 O(n)의 시간이 걸리는데 반해

Linked List는 node가 가르키는 메모리 주소만 바꾸어 주면 되기 때문에 O(1)의 시간이 걸린다.

하지만! 실질적으로 데이터를 삽입,삭제 하려는 인덱스에 도달하기까지의 시간이 O(n) 임으로 O(n)의 시간이 걸린다고 볼 수 있다.

 

특정 인덱스의 데이터 조회

Array는 메모리상에서 연속적이기 때문에 특정 위치를 찍어 데이터의 조회가 가능하다.

Linked List 는 메모리상에서 비연속적임으로 특정 인덱스를 한번에 찾을 수 없다. 따라서 첫번째 node부터 순차적으로 다음 node를 확인하여 특정 인덱스에 도달하여야 한다.

 

Array vs Linked List

	Array	Linked List
중간 삽입, 중간 삭제	O(n)	O(1)
조회	O(1)	O(n)

 

결론

데이터의 갯수가 불확실하고 삽입 삭제가 자주 이루어 지는 경우 Linked list 를 사용하자.

데이터의 갯수가 정해져있고 데이터의 조회를 많이 하는 경우 Array를 사용하자.