[ JAVA ] 자료구조 - 배열( Array )과 리스트 ( List )

배열 ( Array )

>> 선형 자료구조( Data Structure ) 중 하나로, 동일한 타입의 데이터들을 메모리에 연속적으로 저장하여 하나의 변수에 묶어서 관리하기 위한 자료구조이다. index 와 값의 쌍으로 구성되어있다.

• index 는 값에 대한 유일한 식별자 역할을 한다. index로 해당 원소에 접근할 수 있다.
• 연속된 메모리의 공간으로 이루어져 있으며, 배열을 정의할 때 길이를 지정한다.

특징

• 인덱스를 통해 검색이 용이하며, 메모리의 공간이 연속적이므로 메모리 관리가 편리하다.
• 저장된 메모리를 검색할 때 매우 용이하다.
• 메모리의 길이가 고정되어 있기 때문에, 어떤 공간의 원소가 삭제되어도 공간은 유지된다. > 메모리를 효율적으로 사용하지 못한다.
• 컴파일 이후 배열의 크기를 바꾸지 못한다.

 

리스트 ( List )

• 순서가 있는 원소들의 모임이다. 
• 배열과는 다르게 빈 원소는 허용하지 않는다.
• 리스트에서 인덱스는 몇 번째 데이터인가 순서의 의미를 가진다. 배열처럼 값에 대한 유일한 식별자와 같은 역할은 하지 않는다.
• 불연속적으로 메모리 공간을 차지하며, 데이터에 접근하기 위해 포인터를 이용한다.

특징

• 포인터를 통하여 다음 데이터의 위치를 가리키고 있어 삽입,삭제가 용이하다.
• 정적인 배열과 달리 리스트는 동적이므로 크기가 따로 정해져있지 않다. 그러므로 메모리의 관리가 편리하다.
• 배열처럼 연속적으로 메모리 주소를 할당받지 않기 때문에 임의 접근이 불가능하다. 그러므로 검색 성능이 좋지 않으며, 포인터를 통해 다음 데이터를 가리키므로 추가적인 메모리 공간이 발생한다.

ArrayList 

>> ArrayList는 일반 배열과 같이 인덱스로 객체를 관리한다는 점에서 동일하다. 하지만 일반 배열과 달리 리스트처럼 동적으로 크기를 바꿀 수 있다는 특징도 존재한다. 

• 배열은 제너릭을 사용할 수 없지만, arraylist는 타입 안정성을 보장해주는 제너릭을 사용할 수 있다.
• 배열은 원소를 할당하기 위해 할당( assignment )연산자를 사용하지만, arraylist는 add() 매서드를 통해 원소를 삽입한다.

ArrayList의 삽입 / 삭제 과정

[ 삽입 ]

1. List의 크기를 삽입되는 자료의 크기만큼 늘린다.
2. 삽입될 자료의 위치를 기준으로 기존의 데이터들의 순서를 뒤로 이동시킨다.
3. 해당 위치에 자료를 입력한다.

[ 삭제 ]

1. 삭제될 자료가 위치한 인덱스의 자료를 삭제한다.
2. 삭제한 자료의 인덱스를 기준으로 이후의 자료들을 앞으로 이동시킨다.
3. 리스트의 맨 마지막은 비어있는 상태가 된다.

LinkedList 

>> 노드( Node )간의 연결을 통해서 리스트로 구현된 객체이다. 

• ArrayList와 달리 인덱스를 가지고 있지 않으며, 다음 노드의 위치에 대한 정보만을 가지고 있기 때문에 특정 위치의 원소에 접근하기 위해서 순차접근 방식을 사용한다.
• 그러므로 검색시 시간이 많이 소요된다는 단점이 있다.
• 하지만 데이터 추가 / 삭제시  성능이 좋다. ( 위치정보의 수정만으로 가능하기 때문 ).

ArrayList의 삽입 / 삭제 과정

[ 삽입 ]

1. 추가될 자료의 node를 생성한다.
2.  추가될 자료의 해당 인덱스 이전의 node의 다음 node를 추가될 node로 설정한다.
3.  추가될 node의 다음 node를 인덱스 이전 node의 다음 node로 설정한다.

[ 삭제 ]

삭제할 node의 이전 node의 다음 node를 삭제할 node의 다음 node로 설정한다.

 

 

 

[ 참고 ]

https://velog.io/@adam2/Array%EC%99%80-List%EA%B7%B8%EB%A6%AC%EA%B3%A0-Java-List

https://m.blog.naver.com/raylee00/221944085465