[TIL]240518 LinkedList

LinkedList

• 자바의 Linked List는 ArrayList와 같이 인덱스로 접근하여 조회 / 삽입이 가능하지만 내부 구조는 완전히 다르게 구성되어 있다는 점이 특징이다.
• ArrayList는 내부적으로 배열을 이용하여 메서드로 이리저리 조작이 가능하게 만든 컬렉션이라면, Linked List는 노드(객체) 끼리의 주소 포인터를 서로 가리키며 링크(참조)함으로써 이어지는 구조이다.

→ 객체를 만들면 객체의 주소가 생기게 되는데, 노드마다 각기 객체의 주소를 참조함으로서 연결 형태를 구성하는 것이다.

 

Linked List의 장단점

장점

• 배열의 복사나 재할당 없이 데이터 추가 가능 + 유연한 공간을 갖는다.
• ArrayList는 배열이 꽉 차있는 경우 크기를 늘려 준 다음 데이터를 다시 추가해 주는 과정을 진행해야 했는데 LinkedList는 쓰는 공간만큼만 크기가 늘었다 줄었다 하기 때문에 메모리 측면에서 훨씬 효율적이다.

단점

• 데이터 접근에 대한 시간이 늘어난다.
• 배열(Array List)과 달라, Random Access가 되지 않기 때문에 원하는 노드를 찾아야 하는 경우 O(N)의 시간복잡도가 발생한다는 점이 단점이다.

LinkedList 메서드

boolean add(Object obj) : LinkedList의 마지막에 객체를 추가한다. (성공하면 true)

void addFirst(Object obj) : LinkedList의 맨 앞에 객체(obj)를 추가

void addLast(Objec obj) : LinkedList의 맨 뒤에 객체(obj)를 추가

Object set(int index, Object obj) : 지정한 위치(index)의 객체를 주어진 객체로 바꾼다.

Obejct removeFirst() : 첫번째 노드를 제거

Object removeLast() : 마지막 노드를 제거

Object remove() : LinkedList의 첫 번째 요소를 제거

int size() : LinkedList에 저장된 객체의 개수를 반환한다.

// LinkedList 생성
        LinkedList<String> list = new LinkedList<>();

        // 요소 추가
        list.add("Apple");
        list.add("Banana");
        list.add("Cherry");

        // 첫 번째 위치에 요소 추가
        list.addFirst("FirstElement");

        // 마지막 위치에 요소 추가
        list.addLast("LastElement");

        // 특정 위치의 요소 교체
        list.set(2, "Blueberry");

        // 특정 위치의 요소 제거
        list.remove(3);

        // 리스트의 첫 번째 요소 제거
        list.removeFirst();

        // 리스트의 마지막 요소 제거
        list.removeLast();

        // 리스트 크기 확인
        int size = list.size();

 

 

참고 자료

- https://hstory0208.tistory.com/entry/Java%EC%9E%90%EB%B0%94-LinkedList-%ED%81%B4%EB%9E%98%EC%8A%A4-%EC%82%AC%EC%9A%A9%EB%B2%95

- https://cdragon.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-LinkedList%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8