[자료구조/java] List 인터페이스

List(리스트)

일련의 동일한 타입의 항목들이 나열된 형태의 자료구조

- 따라서 순서를 가지게 된다.

 

Java의 컬렉션에서 List 인터페이스를 implement를 하는 클래스는 다음과 같다  [컬렉션포스팅]

• ArrayList 
• LinkedList
• Vector
  • Stack

 

그럼 나열된 자료구조로 배열과 다를 것이 없어 보이지만

배열과 다른점이 존재한다.

배열	List
정적할당( 처음선언한 배열의 크기 변경불가)	동적 할당 (리스트의 길이는 가변길이)
메모리에 연속적으로 나열되어 할당	데이터가 연속적으로 나열되나 메모리에 연속적으로 나열되지 않으며 각 데이터는 주소로 연결되어있음 (ArrayList는 제외)

 

ArrayList

리스트를 배열로 구현한 클래스로 

배열을 이용하기 때문에 인덱스를 이용하여 조회를 하는 것은빠르나

삽입/삭제과정에서 요소에 빈공간이 생기지 않도록 이동하기 때문에 삽입/삭제는 느리다.

 

조회를 많이 하는 경우에는 추천되는 자료구조이다.

 

LinkedList

 

동적 메모리 할당을 이용해 리스트를 구현하는 자료구조로써

즉, 동적 메모리 할당을 받아 노드(Node)를 만들어 사용한다.

종류는 아래와 같다

• 단순 연결리스트(Singly Linked List) - 단방향 연결리스트
  • 노드에 다음노드에 대한 주소가 존재한다.
• 이중 연결 리스트(Doubly Linked List) - 양방향 연결리스트
  • 노드에 2개를 저장하며 이전노드와 다음노드의 주소가 존재한다.
• 원형 연결 리스트 (Circular Linked List)
  • 마지막 노드가 첫 노드와 연결된 단순 연결 리스트

삽입과 삭제에 추천되는 자료구조 이다.

 

Vector

ArrayList와 크게다르지 않지만 Vector하면 동기화가 장점이라는 점을 알 수 있다.