자료구조 배열과 리스트에대해 더 알아보기

  배열

같은 타입의 데이터를 나열한 선형 자료구조이다. 연속된 메모리공간에 순차적으로 저장하며 처음 배열을 선언할때의  크기로 고정이되며 한번 지정된 크기는 줄일수도 늘릴수도없다.

배열의 장점

- 인덱스를 가지고 있어 바로 접근이 가능하다.
- 연속된 메모리공간에 존재하기 때문에 관리가 편하다.

배열의 단점

- 삽입과 삭제가 어렵고 오래걸린다.
  > 원소를 삽입하거나 삭제할 경우, 연속된 메모리공간에 저장되기에 해당 원소 이후의 모든 원소들을 한칸씩 밀거나 당겨야한다.
- 배열의 크기를 수정 할 수 없다.
  > 배열은 처음 생성 할 때 크기를 지정하여 설정하기때문에 유연하게 변경하기에 어렵다.
  > 크기를 변경하기 위해서는 원하는 크기의 새로운 배열을 선언한 뒤 값을 복사해야한다.
- 연속된 메모리라서 중간에 데이터가 삭제되면 빈공간이 생기며 공간낭비가 발생한다.
- 처음 배열을 선언할때 확실한 크기를 몰라 100으로 어림짐작하고 크기를 정하면 나중에 사용할때는 10을 사용해 공간 낭비가 발생하고, 또는 100이상을 필요로해하면 수정하는데에 불편함을 겪는다.

언제 사용하면 좋을까

 : 데이터의 개수가 확실하고 데이터의 삭제,삽입이 적을때. 또는 검색을 자주 다루어야할때

 

 

  연결 리스트

데이터를 순차적으로 저장하는 선형자료구조이다. 불연속적인 메모리 저장공간에 저장하여 데이터를 빈틈없이 사용 할 수 있다.
노드와 노드를 연결하여 만든 리스트이다. 첫번째 노드를 헤드라고부르며 마지막노드를 테일이라 부르며, 각각의 노드는 데이터와 다음노드 가리키는 포인터로 이루어져있다.
크기가 고정되어있지 않고 새로운 요소의 크기가 정해져있지 않으므로 새로운 요소가 추가될때 크기제한으로부터 자유롭다.

연결 리스트의 장점

- 포인터로 연결되어있어 포인터가 가리키는 노드만 변경해주면되므로 삽입과 삭제가 용이하다.
- 크기가 정해져 있지 않고 동적으로 생성된다.
- 연속적인 메모리 할당이 필요하지 않는다.
- 사용한 메모리를 재사용 가능

연결 리스트의 단점

- 반복자를 이용해 탐색하기때문에 검색성능은 좋지못하다.
- 포인터로 인하여 저장공간의 낭비가 발생한다.
- 인덱스 접근이 불가능하다.

언제 사용하면 좋을까

: 크기가 정해져있으며 삽입과 삭제가 빈번히 발생할때 그리고 검색을 자주 사용하지 않을때