정말 오랜만에 백준을 풀면서, 1158 요세푸스 문제를 풀고 있었는데,
리스트에서 요소를 삭제해가면서 다시 loop 하는 방식을 구현해야 하는데, 일반적인 방법으로는 너무 지저분한 코드가 만들어지는 것이다!
찾아보니 원래 이 문제의 목적 자체가 linked list를 이해하는 것이라고 한다.
사실 2학년때 자료구조 배우면서 다 배웠는데(지금으로 부터 약 2년전...)다 까먹었다. 핳! 복습 좀 해둘껄 결국....전공 과목을 이렇게 다시 배워야 하는 처지다ㅠㅠ
그래서 개념을 다시 정리해두려고 한다.
시작!
LinkedList 컬렉션
자바의 LinkedList는 ArrayList와 같이 인덱스로 접근하여 조회, 삽입이 가능하지만, 노드(객체)끼리의 주소 포인터로 서로를 가리키며 링크를 참조함으로써 이어지는 구조를 가지고 있다는 점에서 차이가 있다.
포인터는, 객체의 주소값을 가리키는 화살표 라고 보면 된다!(이 부분은 설명 없이 걍 아는 내용 적은거라 개념이 명확하기 않을 수 있다!)
예를 들어, 단일 노드는 이런식의 구조로 되어 있다고 보면 된다.
class Node {
Node next; // 다음 노드 주소를 저장하는 필드
int data; // 데이터를 저장하는 필드
};단방향 연결 리스트 (singly linked list)
위의 예시처럼 다음 노드를 가리키기 위한 포인터 필드(next)만을 가지고 있는 링크드 리스트를 single linked list라고 한다. 하지만 단일 연결 리스트는 현재 료소에서 이전 요소로 접근해야 할때 매우 부적합한 특징이 있다. 바로 구조상 뒤로가기가 불가능하기 때문이다.
이를 해결하기 위해 만들어진것이 바로 양방향 연결 리스트이다.
양방향 연결 리스트(doubly linked list)
class Node {
Node next; // 다음 노드 주소를 저장하는 필드
Node prev; // 이전 노드 주소를 저장하는 필드
int data; // 데이터를 저장하는 필드
};구조 자체는 많이 바뀌지 않았다. 단지 이전 노드 주소를 저장하는 필드인 prev가 추가 되었다는 것이 차이점이다!
양방향 연결 리스트(doubly circular linked list)
첫번째 노드와 마지막 노드를 연결시켜 원형 리스트처럼 만든 것이다.
내가 풀고자 하는 요세푸스 문제의 경우 이것을 이용한다.
Java에서 사용하기!
LinkedList 객체 생성하기
// 타입설정 int 타입만 적재 가능
LinkedList<Integer> list = new LinkedList<>();
// 생성시 초기값 설정
LinkedList<Integer> list2 = new LinkedList<Integer>(Arrays.asList(1,2));ArrayList의 경우 초기값을 미리 지정하는 것이 가능하지만, LinkedList는 동적으로 움직이기 때문에 데이터가 추가될 때마다 노드(객체)들이 생성되어 동적으로 추가되는 방식을 가진다.
LinkedList 요소 추가/삽입
add의 종류는 여러가지가 존재한다.(뭐...첫번째에 삽입...마지막에 삽입 등..) 이 부분은 그때그때 원하는 메서드를 찾아서 적용하면 되겠다.
이 컬렉션의 가장 큰 특징은, ArrayList와 다르게 중간에 데이터가 추가되거나 중간에 있는 데이터가 삭제되어도 뒤로 미는 등의 행위가 존재하지 않는다는 것이다. 단지 참조값 주소만 다시 설정해서 연결해 주면 된다.
remove 역시 여러가지가 존재하기 때문에(index 값을 제거...등)원하는 것을 선택하면 된다.
이외에도 set으로 값 설정, get으로 값 가져오기 등 여러가지 기능이 존재한다. 필요할때마다 서치 후 사용하면 되겠다!
⭐LinkedList iterator
LinkedList의 상위 인터페이스인 Collection 인터페이스에서는 Iterator 인터페이스를 구현한 클래스의 인스턴스를 반환하는 iterator 메소드를 정의하여 각 요소에 접근하도록 정의하고 있다. 따라서 LinkedList에서도 iterator로 루프 기능을 사용할 수 있다. 예를 들면 다음과 같다.
Iterator it = list.iterator(); //iterator method 사용
while(it.hasNext()) { //다음 값이 있으면 print
Object obj = it.next();
System.out.println(obj);
}뿐만 아니라 ListIterator라는 것도 지원하는데, 이거 같은 경우는 다음값인 next 뿐 아니라 prev 값도 가져올 수 있다. 다음과 같이 사용한다.
ListIterator it = list.listIterator(); // LinkedList의 ListIterator를 반환한다
while(it.hasNext()) {
System.out.print(it.next());
}
while(it.hasPrevious()) {
System.out.print(it.previous());
}이 외에 구조 특성상 Stack이나 Queue로서도 이용이 가능하다. 마찬가지로, 여기서 사용하는 peek나 push등도 사용이 가능하다.
(Stack이나 Queue에 대해서는 차후 한 번더 정리할 예정이다.)
✅ 참고
