[Java] 링크드리스트 (LinkedList) 자료구조

📌 링크드리스트(LinkedList)란?

• Collection framework의 일부이며 java.util 패키지에 소속되어 있다.
• 데이터가 연속된 위치에 저장되지 않고 모든 데이터가 데이터와 주소 부분을 별도로 가지고 있다.
• 포인터와 주소를 이용하여 연결한다.
• 중간에 데이터를 추가나 삭제하더라도 전체의 인덱스가 한 칸씩 뒤로 밀리거나 당겨지는 일이 없다.
• ArrayList에 비해서 데이터의 추가나 삭제가 용이하지만, 인덱스가 없기에 특정 요소에 접근하기 위해서는 순차 탐색이 필요로 하여 탐색 속도가 떨어진다는 단점이 있습니다.
• 가장 첫 번째 노드를 HEAD 노드라 하고, 가장 마지막 노드를 TAIL 노드라고 합니다.

📌 링크드리스트(LinkedList) 선언

// 선언 방식
LinkedList<Integer> linkedList = new LinkedList<Integer>();

// 타입 선언 생략도 가능
LinkedList<Integer> linkedList2 = new LinkedList<>(); 

// 초기 값 세팅
LinkedList<Integer> linkedList3 = new LinkedList<>(List.of(1, 2, 3, 4, 5));
        
// 앞에 List 인터페이스를 활용하여 생성
List<Integer> linkedList4 = new LinkedList<>();

📌 링크드리스트(LinkedList) 값 추가

LinkedList<Integer> linkedList = new LinkedList<Integer>();
linkedList.add(1); // 마지막에 값 추가
linkedList.add(3);
linkedList.addFirst(); // 첫번째 값 추가
linkedList.addLast(); // 마지막 값 추가

// 해당하는 index에 값 추가
linkedList.add(1, 5);

• LinkeList는 내부적으로 값을 추가하면 그림과 같다.
• 인자로 받은 값을 가지고 Node를 생성하여 생성한 노드는 이전 노드는 추가되는 노드를 가리키게 하고 추가되는 노드는 그다음 노드를 가리키도록 지정합니다.

📌 링크드리스트(LinkedList) 값 삭제

LinkedList<Integer> linkedList = new LinkedList<Integer>(List.of(1, 2, 3, 4, 5));
linkedList.removeFirst(); // 첫번째 값 삭제
linkedList.removeLast(); // 마지막 값 삭제
linkedList.remove(); // 첫번째 값 삭제
linkedList.remove(1); // 해당 index 데이터 삭제
linkedList.clear(); // 모두 삭제

• 삭제 대상 노드의 이전의 노드가 삭제 대상 노드의 다음의 노드를 가리키게 하고 해당 노드는 삭제됩니다.