20. List 인터페이스 ArrayList, LinkedList

List 인터페이스에는 객체를 순서에 따라 저장하고 유지하는 데 필요한 메소드가 선언되어 있십니다.

우리가 알고 있는 순차 자료 구조의 대표적인 예는 배열입니다. 

자바에서 배열을 구현한 대표 클래스로는 ArrayList, Vector가 있고, 배열과 구현 방식은 다르지만 순차 자료 구조를 구현한 LinkedList가 있습니다. 그러면 객체 배열로 가장 많이 사용하고 기존 예제이서도 자주 활용한 ArrayList부터 자세히 살펴보겠습니다.

 

ArrayList를 활용해 회원 관리 프로그램 구현하기

 

ArrayList를 사용하려면 import java.util.ArrayList를 선언해 주어야 합니다. 9행에서 ArrayList를 선언하고 MemberArrayList() 생성자에서 ArrayList를 생성합니다. 15~17행 addMember() 메소드에서는 매개변수로 전달된 회원을 ArrayList의 맨 뒤에 추가합니다. 19~31행 removeMember() 메소드에서는 매개변수로 전달받은 아이디(memberid) 회원을 ArrayList에서 찾아 제거합니다.

 

 

14~17행 ArrayList에 추가한 회원이 19행 출력문에 의해 출력됩니다. 또한 memberHong의 아이디를 매개변수로 removeMember() 메소드를 호출하여 배열에서 회원 삭제도 잘 수행됨을 알 수 있습니다.

 

 

 

LinkedList 클래스

배열은 처음 배열을 생성할 때 정적 크기로 선언하고, 물리적 순서와 논리적 순서가 동일합니다. 배열은 중간에 자료를 삽입하거나 삭제할 때 나머지 자료를 이동시켜 빈 공간을 만들지 않고 연속된 자료 구조를 구현합니다. 또한 처음 선언한 배열 크기 이상으로 요소가 추가되는 경우에는 크기가 더 큰 배열을 새로 생성하여 각 요소를 복사해야 하는 번거로움이 있습니다. 이런 점을 개선한 자료 구조를 링크드 리스트(linked list)라고 합니다. 자바의 LinkedList클래스가 이를 구현하고 있습니다. 그러면 링크드 리스트 자료 구조에 대해 간략하게 살펴보고 자바에서 LinkedList 클래스를 활용한 예제를 보겠습니다.

 

 

링크드 리스트 구조

링크드 리스트의 각 요소는 다음 요소를 가리키는 주소 값을 가집니다. 따라서 물리적인 메모리는 떨어져 있어도 논리적으로는 앞뒤 순서가 있습니다. 같은 List 인터페이스를 구현한 ArrayList에 비해 중간에 자료를 넣고 제거하는데 시간이 적게 걸린다는 장점이 있고, 크기를 동적으로 증가시킬 수 있습니다. 링크드 리스트의 각 요소는 요소의 자료와 다음 요소의 주소를 저장하는 부분으로 구현됩니다.

 

각 요소는 물리적으로 다른 메모리에 생서되어 있지만,  다음 요소를 가리키는 순서에 따라 A 다음은 B, 그다음은 C가 됩니다. C의 다음은 가리키는 요소가 없기 때문에 널(null; 아무것도 없음)값이나 0을 저장합니다.

 

LinkedList 사용하기

 

 

LinkedList 클래스에는 링크드 리스트의 맨 앞 또는 맨 뒤에 요소를 추가 삭제하는  addFirst(), addLast(), removeFirst(), removeLast() 등의 메소드가 있습니다.

 

ArrayList로 스택과 큐 구현하기

프로그램을 개발할 때 가장 많이 사용하는 자료 구조인 스택과 큐에 대해 살펴봅시다.

먼저 스택은 상자를 쌓듯이 자료를 관리하는 방식입니다. 스택은 맨 나중에 추가된 데이터를 먼저 꺼내는 (Last In First Out; LIFO)방식입니다. 큐는 일상생활에서 가장 많이 사용하는 방식의 자료 구조로 '선착순'을 생각하면 됩니다.

줄을 선 대기열처럼 먼저 추가된 데이터부터 꺼내서 사용하는 방식(First In First Out; FIFO)입니다.

 

 

ArrayList로 스택 구현하기

 

8~10행 push()에서는 add() 메소드를 사용하여 ArrayList 맨 뒤에 요소를 추가합니다. 그리고 pop() 메소드의 19행 에서 arrayStack.remove(len-1)을 사용해 가장 최근에 추가된 마지막 항목(요소)을 ArrayList에서 제거하고 반환해 줍니다. 테스트 프로그램을 통해 추가된 순서와 반대로 최근 항목부터 pop()이 수행됨을 알 수 있습니다.

 

 

ArrayList로 큐 구현하기

 

8~10행 enQueue()에서는 add() 메소드를 사용하여 ArrayList 맨 뒤에 요소를 추가합니다. 그리고 큐에서 자료를 꺼내는 11~21행의 deQueue() 메소드는 ArrayList의 맨 앞에있는 요소부터 제거하고 반환합니다. 출력 결과를 보면 추가된 순서대로 요소가 반환되는 것을 알 수 있습니다

 

Collection 요소를 순회하는 Iterrator

MemberArrayList.java의 removeMember() 메소드를 보면 for문과 get(i) 메소드를 사용하여 회원을 순차적으로 하나씩 꺼내면서 매개변수와 같은 아이디를 찾습니다. 그런데 순서가 없는 Set 인터페이스를 구현한 경우에는 get(i) 메소드를 사용할 수 없습니다. 이때 Iterator를 사용합니다. Iterator는 Collection 인터페이스를 ㅜㄱ현한 객체에서 미리 정의되어 있는 iterator() 메소드를 호출하여 참조합니다. 예를 들어 Collection을 구현한 ArrayList에 iterator() 메소드를 호출하면 Iterator()클래스가 반환되므로 다음처럼 Iterator형 변수에 대입해 사용합니다.