리스트(List) - 배열 리스트(Array List), 링크드 리스트(Linked List)

리스트(List)

리스트(List)란 컬렉션 프레임 워크의 하위 클래스 중 하나로, 데이터의 순서를 유지하며, 중복된 데이터를 저장할 수 있는 데이터 처리 클래스이다.

리스트의 종류에는 배열 리스트(Array List)와 링크드 리스트(Linked List)가 있다.

 

배열(Array) vs 리스트(List)

속도의 차이는 적기 때문에 보통은 배열 대신 메모리를 아껴쓸 수 있는 리스트를 많이 사용한다.

 

배열 리스트(Array List)

배열 리스트는 인덱스로 관리된다. 배열 리스트는 배열과 유사한 방법으로 관리할 수 있다.

 

링크드 리스트(Linked List)

링크드 리스트는 링크로 연결된 노드의 집합이다.

head로부터 링크를 따라 가면서 데이터에 접근할 수 있다.

 

노드(Node)

각 노드는 자신이 나타내는 데이터와 다음 노드로의 링크를 가지고 있다.

링크에는 다음 노드의 주소값이 담겨 있다.

 

노드(Node)의 추가와 삭제

새로운 노드(Node) 추가

새로운 노드는 다음 순서대로 생성된다.

첫번째 노드와 두번째 노드 사이에 신규 노드를 생성한다고 가정해보자.

1. 새로운 노드와 두번째 노드 사이에 링크를 생성한다.
2. 첫번째 노드와 두번째 노드 사이의 링크를 제거한다.
3. 첫번째 노드의 링크를 새로운 노드로 향하도록 변경한다.

 

기존 노드(Node) 삭제

기존 노드는 다음 순서대로 삭제된다.

첫번째 노드와 세번째 노드 사이의 두번째 노드를 삭제한다고 가정해보자.

1. 첫번째 노드의 링크를 세번째 노드로 향하도록 변경한다.
2. 첫번째 노드에서 삭제할 노드로 가는 링크를 제거한다.
3. 삭제할 노드에서 세번째 노드로 가는 링크를 제거한다.