Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - LinkedList

들어가며

• 해당 내용은 앞 글인 Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - ArrayList, LinkedList에서 이어진다.
• 이번 글에서는 Sequence Container에 속하는 LinkedList를 알아볼 것이다.

2023.01.15 - [Algorithm/Before Check] - Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - (1)

Java에서 알고리즘 풀이 시 자주 사용하는 Collection들 - (1)

 

 

LinkedList

• 연결 리스트라고 부르는 LinkedList는 자료구조에 대해 배운 사람이라면 누구나 알고 있을 법한 자료구조이다.
• LinkedList는 Node라고 부르는 컨테이너에 데이터를 넣으며 이 Node는 자신의 뒷 Node의 주소를 가지고 있다.
• 따라서 데이터의 삽입 삭제가 빠르다. 그 이유는 Node의 주소를 가진 참조변수를 조작하여 Node를 붙이거나 때는 것으로 데이터 삽입 삭제 연산을 구현할 수 있기 때문이다.
• 메모리상에 차지하는 공간이 연속적이지 않고 분포되어있기 때문에 배열과 같은 접근이 불가능하다.
• Java에서의 LinkedList는 한쪽으로만 순회할 수 있는 단방향 LinkedList가 아닌 양방향으로 순회가 가능한 양방향 LinkedList이다.
• LinkedList의 기본적인 연산은 다음과 같다.

메서드	메서드 타입	설명
LinkedList()	constructor	LinkedList 객체를 생성하여 반환한다.
LinkedList(Collection c)	constructor	컬랙션의 모든 요소를 가진 LinkedList 객체를 생성하여 반환한다.
add(E e)	boolean	객체 e를 추가한다.
add(int idx, E e)	void	LinkedList의 idx위치에 객체 e를 추가한다.
addAll(Collection c)	boolean	컬랙션의 모든 요소를 LinkedList에 추가한다.(LinkedList의 마지막부터)
addAll(int idx, Collection c)	boolean	컬랙션의 모든 요소를 LinkedList에 추가한다.(지정된 위치 idx부터)
addFirst(E e)	void	LinkedList의 head에 객체 e를 추가한다.
addLast(E e)	void	LinkedList의 tail에 객체 e를 추가한다.
clear()	void	LinkedList의 모든 요소를 제거한다.
get(int idx)	E	LinkedList의 idx번째 객체를 가져온다.
getFirst()	E	LinkedList의 첫 번째 객체를 가져온다.
getLast()	E	LinkedList의 마지막 객체를 가져온다.
indexOf(Object o)	int	객체가 LinkedList의 어느 위치에 있는지 찾아 그 위치를 반환한다. 존재하지 않을 시 -1를 반환한다. head -> tail 방향으로 찾는다.
lastIndexOf(Object o)	int	객체가 LinkedList의 어느 위치에 있는지 찾아 그 위치를 반환한다. 존재하지 않을 시 -1를 반환한다. tail -> head 방향으로 찾는다.
listIterator(int idx)	ListIterator	LinkedList의 모든 요소를 순회하는 ListIterator를 반환한다.
descendingIterator()	Iterator	LinkedList의 모든 요소를 역방향으로 순회하는 Iterator를 반환한다.
peekFirst()	E	LinkedList의 첫 번째 요소를 가져온다.
peekLast()	E	LinkedList의 마지막 요소를 가져온다.
pollFirst()	E	LinkedList의 첫 번째 요소를 제거하고 그 요소를 반환한다.
pollLast()	E	LinkedList의 마지막 요소를 제거하고 그 요소를 반환한다.
removeFirst()	E	LinkedList의 첫 번째 요소를 제거하고 그 요소를 반환한다.
removeLast()	E	LinkedList의 마지막 요소를 제거하고 그 요소를 반환한다.
toArray()	Object[]	LinkedList의 요소들을 배열에 넣어 그 배열을 반환한다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class StudyCode {
    static LinkedList<Integer> list;

    public static void main(String[] args) throws Exception{
        list = new LinkedList<>();

        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);
        list.add(1, 5);

        System.out.println(list.peekFirst());
        System.out.println(list.peekLast());
        
        printElement();

        System.out.println();

        list.pollFirst();
        list.pollLast();

        list.remove(2);
        list.remove(2);

        printElement();
        printReverseElement();
    }

    static void printElement(){
        ListIterator<Integer> iter = list.listIterator();

        while(iter.hasNext()){
            System.out.print(iter.next() + " ");
        }
        System.out.println();
    }

    static void printReverseElement(){
        Iterator<Integer> iter = list.descendingIterator();

        while(iter.hasNext()){
            System.out.print(iter.next() + " ");
        }
        System.out.println();
    }
}