LinkedList (연결 리스트)
1. LinkedList (연결 리스트)
각 노드가 데이터와 포인터를 가지고 연결되어 있는 방식의 자료구조이다. 연결 리스트의 각 노드들은 자신과 연결된 다음 노드에 대한 참조(주소값)와 데이터로 구성되어 있다. 임의의 위치에 원소를 추가하거나 제거하더라고 전체 인덱스가 밀리거나 당겨지지 않는다. 인덱스가 없기에 임의의 위치에 접근하기 위해서는 순차 탐색이 필요로 하여 O(N)의 시간이 필요하다.
1.1 배열과 연결 리스트
- 배열 연결 리스트 원소의 접근 O(1) O(N) 임의 위치에 원소 추가/제거 O(N) O(1) 메모리 상의 배치 연속 불연속 Overhead - O(N)
1.2 LinkedList 사용법
선언
LinkedList list = new LinkedList();
LinkedList<Integer> num = new LinkedList<Integer>();//타입설정 int타입만 사용가능
LinkedList<Integer> num2 = new LinkedList<>();//new에서 타입 파라미터 생략가능
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));//생성시 값추가연결 리스트 생성시에 사용 타입을 명시해주는 것이 좋다.
원소 추가
import java.util.LinkedList;
LinkedList<Integer> list = new LinkedList<Integer>();
list.addFirst(1);//가장 앞에 데이터 추가
list.addLast(2);//가장 뒤에 데이터 추가
list.add(3);//데이터 추가
list.add(3, 84);//index 3에 데이터 84 추가일반적으로 add(index, value) 메소드를 통해 추가한다. index를 생략하면 가장 마지막에 추가가 된다.
원소 삭제
list.removeFirst(); //가장 앞의 데이터 제거
list.removeLast(); //가장 뒤의 데이터 제거
list.remove(); //생략시 0번째 index제거
list.remove(2); //index 2 제거
list.clear(); //모든 값 제거추가와 비슷하다. clear() 메소드를 사용한다면 원소가 모두 제거 된다.
연결 리스트 크기 구하기
LinkedList<Integer> list = new LinkedList<Integer>(Arrays.asList(1,2,3));
System.out.println(list.size()); //list 크기 : 3관련 메소드 정리
생성자 또는 메소드 설명 LinkedList() LinkedList객체 생성 add(int index, Object element) 지정된 index에 element 추가 remove() index의 원소 제거 clear() 모든 원소 삭제 contains() LinkedList에 포함되면 true get(int index) index return indexOf() 저장된 index(앞에서 몇 번째)를 return isEmpty() LinkedList가 비어있으면 true Iterator iterator() Iterator 반환 **ListIterator listIterator() ListIterator 반환** size() LinkedList의 크기
2. Iterator/ListIterator
2.1 Iterator
자바의 컬렉션 프레임워크는 컬렉션에 저장된 요소를 읽어오는 방법을 Iterator 인터페이스로 표준화 하고 있다.
Collection 인터페이스를 상속받는 List와 Set 인터페이스에서도 iterator() 메소드 사용이 가능하다.
전체 객체를 대상으로 한 번씩 반복해서 가져오는 반복자(Iterator) Iterator 인터페이스를 구현한 객체는 iterator() 메소드를 호출하면 얻을 수 있다.
메소드
메소드 설명 hasNext() iteration이 다음 요소를 가지고 있으면 true next() iteration의 다음 요소 return remove() 컬렉션에서 객체 제거
2.2 ListIterator
ListIterator는 Iterator 인터페이스를 상속받아 여러 기능이 추가된 인터페이스이다.
Iterator는 컬렉션의 요소 접근이 한 방향이지만, ListIterator는 컬렉션 요소의 대체, 추가, 검색 등을 위한 작업에서 양방향 이동이 가능하다.
메소드
메소드 설명 add() 해당 리스트에 전달된 요소 추가 hasNext() 해당 리스트를 순방향으로 순회할 때 다음 요소가 있다면 true hasPrevious() 해당 리스트를 역방향으로 순회할 때 다음 요소가 있다면 true next() 리스트의 다음 요소 반환, 커서의 위치를 순방향으로 이동 nextIndex() next() 메소드를 호출하면 반환될 요소의 인덱스 return previous() 리스트의 이전 요소 반환, 커서의 위치를 역방향으로 이동 previousIndex() previous() 메소드를 호출하면 반환될 요소의 인덱스 return remove() next()나 previous() 메소드에 의해 반환된 가장 마지막 요소를 제거 set(E e) next()나 previous() 메소드에 의해 반환된 가장 마지막 요소를 전달된 객체로 대체
참고
자바의 정석
https://blog.encrypted.gg/932
https://coding-factory.tistory.com/552
https://minhamina.tistory.com/18
