선형 자료구조의 한 종류인 리스트는 배열 리스트(Array List)와 연결 리스트(Linked List)로 나뉜다. 

# 배열 리스트 ( Array List ) 

: 배열 기반으로 구현된 리스트.

장점

- index를 이용한 랜덤 접근 지원

단점

- 처음에 길이를 정해줘야 하며 필요에 따라 길이를 변경할 수 없다. ( 고정 길이 )

- 추가/삭제 시 나머지 요소들의 이동이 필요하다.

# 연결 리스트 ( Linked List ) 

: 메모리에 동적할당된 공간에 데이터를 저장하고, 그 공간들을 연결해서 구현한 리스트다. 

장점

- 처음에 길이를 정할 필요가 없고 각 요소는 메모리에 동적할되므로 길이 제한에 자유롭다. ( 가변 길이 )

- 추가/삭제 시 나머지 요소들의 이동이 필요없다.

단점

- 순차 접근으로 시간 복잡도 증가.

# 자바의 Array List

: Java Collection에서도 Array List, Linked List같은 리스트 자료구조를 제공하는데, 이 중 Array List는 이름을 그대로 해석하면 "배열 리스트"지만 기존 배열기반 리스트의 단점을 보완한 특징을 가진다.

장점 

- 처음에 길이를 정할 필요가 없다. ( 가변 길이 )

- 랜덤 접근 지원.

단점

- 추가/삭제 시 나머지 요소들의 이동이 필요하다.

위 그림에서 8의 중위-후속자는 10, 10의 중위-후속자는 12, 14의 중위-후속자는 20이다.

 출처 http://www.geeksforgeeks.org/inorder-successor-in-binary-search-tree/