[자료 구조] 연결리스트(LinkedList) in java

연결리스트의 구조와 특징

LinkedList를 단일리스트로 설명하는 그림

연결리스트(LinkedList)란? Collection Framwork내에 있는 List 컬렉션 중 하나(List의 일부).

List의 종류 > ArrayList(리스트로 생성되나 성격은 array와 더 비슷하다. 동적배열이라고 생각하면 쉬움), LinkedList

List는 객체 자체를 저장하지 않고 객체의 번지(메모리 주소)를 저장한다. 그러나 이러한 객체의 번지는 array와 ArrayList와 달리 연속적이지 않다. 또한 맨 처음 부분인 head와 맨 끝부분 tail으로 구분 된다.

데이터가 저장된 메모리공간을 대략적으로 그린 그림

위의 그림은 정확하진 않겠지만 데이터들이 Array, ArrayList와 달리연속적으로 저장되지 않는다는 것을 알려주고 싶어 그림을 첨부했다.

 

+ LinkedList 컬렉션은 이중 연결 리스트를 구현한 것이다. 따라서 this.prev, this.next로 연결된 앞과 뒷쪽 모두 접근 가능하다.

 

특징은 삽입, 삭제가 O(1)로 매우 빠르고, 검색과 접근은 O(n)으로 ArrayList에 비해 느리다는 것이다.

연결리스트의 관련 메서드

메서드	기능	시간복잡도
addFirst(Object obj) add(int idex, Object obj) add(Object obj) addLast()	첫번째 위치로 obj를 추가합니다. 지정된 위치(index)에 obj를 추가합니다. 맨 끝에 obj를 추가합니다. 맨 끝에 obj를 추가합니다.	O(1) idx를 찾는 시간 + O(n) O(n) O(1)
removeFirst() remove(Object o) removeAll(Collection c)	첫번째 요소를 반환한 후 삭제합니다.	O(1)
peek() peekFirst()	첫번째 요소(head) 값을 반환합니다.	O(1)
get(int idex)	지정된 위치(index)에 있는 값을 반환합니다.	O(n)

-> 더 많은 메서드가 존재한다.

스택,큐처럼 peek(), poll()등으로 조회와 삭제가 가능하고 First, Last 부분을 구분해주는게 이해가 안됐는데 알고보니 인터페이스 Deque도 상속받는다. !! 인터페이스를 이래서 사용하는구나 싶다. 다중상속이 가능하니 메서드를 이거저거 다양하게, 다형성을 이용할수있겠다.

List와 Deque 인터페이스를 모두 상속받아 만들어지는 LinkedList의 모습

 

연결리스트의 삭제

연결리스트에 데이터 삭제하는 모습

기본 연결리스트에서 data3을 삭제할때 다음과 같이 data2의 next가 data4의 주소로 바뀐 것을 알 수 있다. 

연결리스트의 삽입 

연결리스트에 데이터를 삽입하는 과정

앞전에 연결리스트 그대로 data5를 data1과 data2의 사이에 삽입하고 싶을 때 다음과 같이 data1의 next는 data5의 주소를 가르키고, data5의 next부분이 data2의 주소를 가리키고 있는 것을 알 수 있다.

연결리스트의 구현

import java.util.LinkedList;

LinkedList objList = new LinkedList(); // 제네릭 미사용시 type은 Object다.
LinkedList<String> strList = new LinkedList<String>(); // 주로 제네릭 사용
LinkedList<Integer> intList = new LinkedList<>(); // new에서 타입 생략가능

참고할 만한 문제 :

 https://www.acmicpc.net/problem/1158

1158번: 요세푸스 문제

https://school.programmers.co.kr/learn/courses/30/lessons/42587

프로그래머스