[자료구조] 배열 VS 연속리스트 VS 연결리스트 구분하기

1. 배열

 

-연속적인 메모리 공간에 저장

-크기가 고정

-인덱스로 빠른 조회(O(1))

-삽입/삭제 느림 (O(n))

 

세부분류

• 정적배열: 자바에서 쓰는 방식. 크기가 고정되어 삽입/삭제 시 개발자가 직접 새로운 배열을 생성해 값을 옮겨야 한다. 
• 동적배열: 자바스크립트에서 쓰는 방식. 내부적으로 새로운 배열로 값을 옮겨주므로 개발자가 직접 배열을 생성해 옮길 필요가 없다.

 

 

 

장점:

인덱스로 빠른 조회가능.

메모리 사용 효율적. (연속된 메모리공간)

 

단점:

크기가 고정.

삽입/삭제 시, 기존 요소들을 옮기는 작업으로 오래 걸림  

 

 

 

 

2. 연속 리스트

 

배열처럼 연속된 메모리 공간에 저장하나, 크기 조절 가능.

크기조정 시, 기존데이터를 옮기는 작업이 필요하다 

일반적으로 동적배열과 연속리스트를 구분하지 않는 경우가 많다.

조회-(O(1))

삽입/삭제-(O(n))

 

 

장점:

연속된 메모리공간에 저장되어 인덱스로 빠른 조회 가능. 

크기 조절이 가능하여 프로그램 실행중 동적으로 요소 추가/삭제 가능.

 

단점:

삽입, 삭제시 자료를 이동시켜야하고 오래걸린다

크기를 보통 2배로 늘리는 방식 등으로 크기 조절을 하는데, 이 과정에서 불필요한 메모리 사용 발생.

 

 

 

 

 

 

3.연결 리스트

여러개의 노드로 구성되며, 각 노드는 데이터와 다음 노드에 대한 포인터(링크)로 구성된다.

메모리상에 비연속적으로 저장.

순차적 탐색으로 조회 느림(O(N))

해당 노드의 위치를 알때 삽입/삭제 매우 빠름. 포인터 이동만으로도 가능하기 때문이다 (O(1))

 

-> 따라서 삽입, 삭제가 빈번하게 일어나는 상황에서 사용한다.

 

세부 분류

• 단일 연결 리스트 (Singly Linked List): 각 노드가 다음 노드에 대한 포인터만 가짐
• 이중 연결 리스트 (Doubly Linked List): 각 노드가 이전 및 다음 노드에 대한 포인터를 가짐 (양방향 탐색 가능)
• 원형 연결 리스트 (Circular Linked List): 마지막 노드가 첫 번째 노드를 가리켜 순환 구조 형성

 

 

장점:

삽입, 삭제가 빠르다.

동적 크기 조절 가능.

 

단점:

순차적 접근으로 조회 느림.

각 노드마다 추가적인 메모리 사용

 

 

 

 

 

 

배열내 요소는 삽입,삭제가 안되는가??

 

삽입,삭제 된다 : 크기고정인데?? 그럼 삽입안되고, 삭제는 시간복잡도 몇?

삽입,삭제 안된다 : 삭제는 되잖아. 해당요소에 null값 들어가는거아님??