Array와 더불어 기본적인 자료구조다.
1
Linked List Array와 비슷하게 많은 양의 데이터를 효율적으로 다루기 위해 사용되는 자료구조다.
Linked라는 이름에서 알 수 있듯 각 요소끼리 'Link'된 형태이다. 연결리스트의 요소는 노드라고 부른다. 각 노드가 다음 노드의 주소를 가지고 있는 방식으로 연결된다.
다음 노드의 주소만 가진 단방향 연결리스트와 다음 노드와 이전 노드, 두 가지 주소를 가진 양방향 연결리스트가 있다.
2
연결 리스트의 가장 큰 특징은 메모리 상에 비연속적인 구조로 삽입/삭제가 효율적이다.
Array처럼 생성할 때부터 메모리에 원하는 만큼 자리를 차지하지 않고 각 노드마다 메모리 상에 따로따로 위치하게 된다. 따라서 요소를 삽입/삭제할 때는 앞,뒤 노드의 연결만 바꿔주면 되기 때문에 효율적이다. 따로 요소를 뒤로 밀거나, 앞으로 당기는 작업을 하지 않는다. 시간복잡도로 표현하면 O(1)이다.
3
인덱스가 없기 때문에 요소를 조회하기 위해서 순차적으로 순회해야 한다. 원하는 노드까지 순서대로 타고타고 가야하기 때문에 상대적으로 시간이 많이 걸린다. 시간복잡도로 표현하면 O(n)이다.
양방향 연결리스트의 경우 이전(previous)으로도 이동이 가능하기 때문에 찾고자하는 요소에 따라 head에서 순회를 시작할 수도 tail에서 시작할 수도 있다. 단방향 연결리스트에 비해 조회 성능이 2배 빠르다.
참고
안녕하세요!