[JAVA] LinkedList 사용법

LinkedList란

LinkedList는 List를 상속받은 클래스로, 포인터를 통해 앞뒤 요소가 연결되어 있는 자료구조이다. LinkedList에서는 데이터를 담고있는 노드(node)가 있고, 이 노드의 포인터가 앞 뒤 노드와 연결되어 있다. LinkedList는 배열이나 ArrayList와 달리 인덱스 기반의 접근이 불가능하고 연결된 포인터를 통해서만 요소들에 접근할 수 있다.

LinkedList 사용법

선언하기

LinkedList<Integer> llist = new LinkedList<Integer>();
LinkedList<Integer> llist = new LinkedList<>();

생성자 부분의 제네릭 타입은 생략이 가능하다.

메서드

요소 추가

LinkedList<Integer> llist = new LinkedList<>();

llist.add(100); //맨 뒤에 값 추가
llist.add(300); //맨 뒤에 값 추가
llist.add(1,200); //1번 인덱스에 200이라는 값 추가
llist.addFirst(0); //맨앞에 0이라는 값 추가
llist.addLast(400); //맨 뒤에 400이라는 값 추가

위 사진과 같이 LinkedList 중간에 요소를 추가하면 기존의 포인터 연결을 끊고 B노드의 포인터를 E노드(새로운 노드)에 연결해주고, E노드의 포인터는 C노드에 연결하는 작업이 이루어진다.

요소 삭제

LinkedList<Integer> llist = new LinkedList<>();

llist.remove(2);  //2번 인덱스 값 삭제
llist.removeFirst(); //맨 앞 요소 삭제
llist.removeLast(); //맨 뒤 요소 삭제
llist.clear(); //모든 값 삭제

요소 삭제도 마찬가지로 기존에 연결되어 있던 포인터의 연결을 끊고, 새로운 노드에 연결해주면 된다.

요소 검색

LinkedList<Integer> llist = new LinkedList<>();

llist.get(3); //3번 인덱스의 값 반환
llist.contains(200); //200이라는 값의 존재여부를 boolean으로 반환
llist.indexOf(100); //100이라는 값의 인덱스를 반환, 없다면 -1

LinkedList에서 어떤 요소를 검색하려면 첫 노드에서 시작하여 포인터를 타고 해당 노드까지 검색을 해야한다. 따라서 최악의 경우 O(n)만큼의 시간복잡도를 가진다.

LinkedList 크기

LinkedList<Integer> llist = new LinkedList<>();

int s = llist.size();

정리

LinkedList는 앞 뒤 요소가 포인터로 연결된 자료구조이다
LinkedList는 요소의 삽입과 삭제가 빠르다. O(1)
요소를 검색하기 위한 인덱스가 없으므로 요소 검색시 순차검색이 이루어진다. 따라서 검색에 있어서는 속도가 느리다. worst case-O(n)