LinkedList

LinkedList (연결리스트)

- 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 데이터를 저장하는 자료구조

- 노드의 포인터가 다음, 이전의 노드와의 연결을 담당

- 추가 또는 삭제 시 용이하지만, 특정 위치의 데이터를 검색하는 것은 오래걸린다는 단점

시간 복잡도

- 추가 또는 삭제 : O(1)

- 특정 위치의 데이터 검색 : O(n)

 

LinkedList 의 구조

- 노드(node)와 링크(link)로 구성

- 노드 : 실제 정보를 담고 있음

- 링크 : 노드간 위치 정보를 저장하고 있어 연결리스트의 순서를 유지할 수 있도록 하는 연결고리

- 노드의 시작점은 head, 끝점은 tail

- 노드의 추가, 삭제, 탐색이 가능

 

LinkedList VS Array

- 배열은 각 값마다 고유 인덱스를 가지고 있어 탐색에 매우 유리함

- 하지만 삽입, 삭제 시 인덱스를 앞,뒤로 밀어서 빈자리에 넣어줘야해서 비효율적임

- 연결리스트는 삽입,삭제할 노드 위치의 이전, 다음노드와 연결만 해주면되기 때문에 이러한 배열의 단점을 해결해줄 수 있음

- But, 연결리스트는 탐색하려면 항상 첫번째 노드부터 비교해줘야하는 단점이 있음

따라서

데이터 탐색이 많이 필요하다면 Array

삽입, 삭제가 많이 필요하다면 LinkedList

를 사용하는 것이 효율적이다