[TIL] 자료구조 - 배열, 연속리스트, 연결리스트 차이

 

 

1. 배열

 

고정된 크기의 연속된 메모리공간에 동일한 크기와 타입의 자료를 저장한다

 

특징:

요소들은 동일한 타입을 가진다

크기가 고정되어있고, 변경불가능하다

중간 자료가 삭제되면 null값이 들어간다(밀도 != 1)

 

인덱스 통한 검색 시: ( 시간복잡도: O(1) )

 

장점:

빠른 인덱스접근이 가능하다

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

 

단점:

크기변경이 불가능하다

 

 

 

 

 

 

2.연속 리스트

배열과 유사하게 연속된 공간에 자료를 저장하지만 크기 조절이 가능하다

 

특징:

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

중간자료가 삭제되면 뒤의 자료들을 앞으로 땡겨온다 (밀도=1 )

인덱스 통한 검색시 : O(1)

삽입, 삭제시 :  O(n)

 

장점:

연속된 메모리공간에 저장되어 빠른접근이가능하다 

크기 조절이 가능하다

 

단점:

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

크기 조정시 데이터복사로 인한 오버헤드

ㄴ 크기를 2배로 늘리는 방식을 사용하기 때문에, 불필요한 메모리를 많이 사용하게된다

 

 

 

 

 

3.연결 리스트

여러개의 노드가 모여 형성되는 구조이다.

각 노드는 데이터와 링크(다음 노드에 대한 포인터)부분이 존재한다.

탐색( O(N) )은 느리지만 삽입, 삭제 ( O(1) )는 매우 빠르다.

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

 

단일 연결 리스트는 연결이 단방향으로 되어있어 일방통행과 같은 구조로 되어있는 연결 리스트를 말한다.

 

 

특징: 

비연속적인 공간에 자료들이 저장되며, 각 노드는 다음노드로의 포인터를 포함한다

인덱스 통한 검색시 : O(n)

삽입,삭제시 : O(1)

 

 

장점:

삽입, 삭제가 빠르다( 시간복잡도 : O(1) )

크기조절이 가능하다

 

단점:

접근이 느리다 (시간복잡도 :  O(n) )

추가적인 메모리를 사용한다( 포인터 저장을 위한 메모리)

 

 

 

 

 

 

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

 

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

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

 

 

 

 

 

 

 

문제)

 

배열에서 K번째 요소의 값을 찾는데 걸리는 시간은 O(1)이다 - O

 

삽입, 삭제위치를 안다고 가정할때 단일 연결리스트의 삽입, 삭제시간은 O(n)이다 - O

 

단일 연결 리스트의 끝에 도착하면 다시 뒤로갈 수 없다. - O

 

단일 연결 리스트에서 3이라는 데이터를 들고 있는 노드를 찾는데 걸리는 시간은 O(N)이다. -O

 

배열에서 3이라는 데이터를 들고있는 노드를 찾는데 걸리는 시간은 O(N)이다. - O