[자료구조] 리스트(List/ ArrayList / LinkedList)

List

- 선형 자료구조 

- 순서를 가진 항목들의 모임

- 배열이 가지고 있는 인덱스라는 장점을 버리고 빈틈없는 데이터 적재라는 새로운 장점을 취한 자료구조

- 중복된 데이터의 저장 허용

- ArrayList , LinkedList등 여러 인터페이스를 구현한 자료형이 있다

- 자바스크립트,파이썬 같은 경우에는 리스트를 따로 구현하지 않고 배열에 List의 기능 중 일부를 제공

- List에서는 인덱스가 중요하지 않다

- 리스트의 핵심은 element간의 순서

- 다른말로 순서라는 의미의 시퀀스(sequence)라고도 함

- 수학적으로 유한수열을 표현한 것

기능(operation)

- 처음,끝에 데이터 삽입기능

- 리스트에 데이터가 있는지를 체크하는 기능

- 리스트의 모든 데이터에 접근할 수 있는 기능  

위와 같은 기능을 가지고 있고 순서가 있으면서 중복이 허용되는 자료구조를 리스트(List)라고 함

Java 에서의 List

*자바8의 API 문서에서 List를 검색한 결과

- java.util 패키지의 하위 인터페이스

- Collection<E> 인터페이스와 Iterable<E> 인터페이스를 구현함

- 하위 클래스로 사진 맨밑에줄에 있는 클래스들을 가짐 ....

- 가장 중요한 클래스 : ArrayList , LinkedList

1 ArrayList

- 배열을 이용해서 리스트를 구현한 것을 의미

- 장점 : 내부적으로 배열을 이용하기 때문에 인덱스를 이용하여 접근하는 것이 빠름 

- 단점 : 데이터의 추가/삭제가 느림

- 내부적으로 데이터를 배열에 저장 하므로 배열의 특성상 데이터를 리스트의 처음이나 중간에 저장하면 이후의 데이터들이 한칸씩 뒤로 물러나야 함 

- 삭제 : 빈자리가 생기면 빈자리를 채우기 위해서 순차적으로 한 칸씩 땡겨야 함

- 데이터 가져오기 : 인덱스를 이용하기 때문에 메모리상의 주소를 정확하게 참조 하므로 속도가 매우 빠름

생성 

import java.util.ArrayList ; // import 

ArrayList<> list = new ArrayList<>() ;

추가

- 제네릭 타입을 선언한다면 해당 타입만 추가가능

- 기본적으로 리스트의 맨 뒤에 데이터 추가

- 특정 인덱스를 선택해 해당 위치에 데이터 추가 가능

- 데이터를 추가하는 과정에서 내부적으로 사용하는 배열이 꽉차면 기존의 배열 대비 2배 큰 새로운 배열을 만들고 기존의 데이터를 새로운 배열로 복제

- 사용자는 ArrayList의 크기에 신경쓰지 않고 편리하게 프로그램을 만들 수 있다

list.add(1234);  // list라는 ArrayList 맨뒤에 1234 라는 int타입 데이터를 추가

list.add(9083);  // list라는 ArrayList 맨뒤에 9083 라는 int타입 데이터를 추가

list.add("hello java");  // list라는 ArrayList 맨뒤에 "hello java" 라는 String타입 데이터를 추가

list.add(1,50) ; // 1이라는 인덱스에 50이라는 값을 추가

삭제

list.remove(2) ; // list의 3번째 데이터를 삭제 ( 항상 배열,리스트의 인덱스는 0부터 시작 )

가져오기

list.get(20) ; // 인덱스가 20인 데이터를 가져옴

반복

- 자바에서는 ArrayList를 탐색하기 위한 방법으로 iterator를 제공

- 객체지향 프로그래밍에서 사용하는 방법 기법

- 먼저 Iterator 객체 생성

Iterator it = list.iterator( ) ; // iterator 객체는 list객체의 iterator( ) 메소드를 통해 생성

while(it.hasNext()){  // 다음 엘리먼트가 존재하면 while문 반복

System.out.println(it.next()); // 다음 엘리먼트를 출력

if(it.next() = 1234){  // 다음 엘리먼트가 1234 라면

it.remove();  // 해당 엘리먼트 삭제

}

};

2 LinkedList

- element간 연결(link)을 통해서 리스트를 구현한 것

- 노드(node or vertex)가 사용됨

- head(첫번째 node)와 tail(마지막 node)

- 메모리 제한이 없다

- 자료의 순서를 유지한 채 삽입과 제거가 쉽다

사진 출처: 생활코딩 egoing님 자료구조 강좌(https://opentutorials.org/module/1335/)

노드(Node)

- 노드는 두가지 정보를 가진다

- 노드의 값 (data)

- 다음 노드를 가르키는 참조 값 (next)

Node 구현

LinkedList클래스에서 Node객체와 해당 변수를 사용해야 하므로 public 으로 선언했지만 리스트의 내부부품의 의미로 사용하기 위해서는 Node를 LinkedList의 내부 클래스로 생성하는 것이 더  좋은 방법일 것 같다 

( 아래에 제공된 소스에는 수정해서 첨부 했어요 ) 

LinkedList 또한 자바 내장 객체로 지원되지만 직접 LinkedList 의 기능들을 구현해 보았다

추가

1) 처음에 추가하기 

- head를 새로운 node로 교환하는 것

- 새로운 node의 next를 기존 head로 설정하고 head를 새로운 node로 설정

- 리스트의 크기 증가

- 만약 기존 head가 없다면 head인 동시에 tail로 설정 (or 리스트의 크기가 1이면 head==tail )

2) 마지막에 추가하기

- 새로운 노드를 만들어 tail의 next로 설정

- 다시 새로운 노드를 tail로 설정

- 리스트의 사이즈가 0이면 head에 붙이는 것과 동일

3) 중간에 추가하기

- 추가 하고자 값과 함께 추가 하고자 하는 인덱스를 매개변수로 받는다

- 매개변수로 받은 인덱스가 0이면 head에 추가한다

- 매개변수로 받은 인덱스가 0이 아니면 추가하고자 하는 인덱스의 앞 노드를 임시노드에 받아둔다

- 새 노드의 next를 임시노드의 next로 설정한다

- 임시노드의 next를 새 노드로 설정한다

- 크기 값을 증가시켜준다

LinkedList 소스는 아래 ZIP파일

LinkedList.zip