배열 vs 연결 리스트 차이 그리고 노드, 이중 연결 리스트

노드

연결 리스트는 서로 인접 하지 않은 메모리 셀 묶음으로 이뤄진다.. 컴퓨터 메모리 전체에 걸쳐 여러 셀에 퍼져 있을 수 있다. 서로 인접하지 않은 이러한 셀을 노드라 부른다.

"a"	1652	"b"	1983	"c"	null
1000	1001	1652	1653	1983	1984

 

배열 vs 연결 리스트 차이

- 연결 리스트를 다루는 코드는 항상 첫 번째 노드가 메모리 어디에서 시작하는지 알고 두번째 세번째 링크를 따라 나머지 리스트를 검색할 수 있다.

 

- 연결 리스트가 배열보다 나은 점 중 하나는 프로그램이 데이터를 저장하기 위해 메모리 내에 나란히 이어진 빈 셀 묶음을 찾을 필요가 없다는 점이다.

 

연산	배열	연결 리스트
읽기	O(1)	O(N)
검색	O(N)	O(N)
삽입	O(N)(끝에서 하면 O(1))	O(N)(앞에서 하면 O(1))
삭제	O(N)(끝에서 하면 O(1))	O(N)(앞에서 하면 O(1))

 

검색과 삽입, 삭제는 차이가 거의 없는것처럼 보이고 배열 읽기만 연결 리스트 읽기보다 훨씬 빠르다.

하지만 한 리스트를 검사해서 많은 원소를 삭제할 때는 연결 리스트가 배열보다 훨씬 낫다.

 

예를 들어 메일 주소를 찾아 유효하지않은 이메일 형식을 삭제하려고 할때

 

배열일 경우(메일 1000개)

- 읽기(1000단계) + 삭제 약 100,000단계(유효하지 않은 이메일 100개 * N개)

 

연결 리스트일 경우(메일 1000개)

- 읽기(1000단계) + 삭제 약 100단계(유효하지 않은 이메일 100개)

- 리스트 전체를 살펴보면서 삭제가 필요하면 그저 그 노드의 링크가 적절한 노드를 가르키게바꾸기만하면 되기에

O(1)단계만 걸린다.

 

이중 연결 리스트

연결리스트는 큐와도 조화로운데 큐는 데이터를 리스트 끝에 삽입한다.

삽입일 경우 연결리스트는 O(N)단계, 배열은 O(1)로 배열이 더 효율적이다. 하지만, 큐에서의 삭제는 앞에서부터 삭제하므로 O(N)걸리는 배열과 달리 O(1)걸리는 연결 리스트가 더 효율적이다. 여기서 특수한 연결 리스트 변형을 사용하면 삽입, 삭제도 모두 O(1)단계로 할 수 있다.