[JAVA] LinkedList

 

 

자료구조 ?

데이터를 컴퓨터에서 효율적(실행 시간 최소화, 계산의 간편화 등)으로 사용하도록 해주는 알고리즘

LinkedList ?

노드(데이터와 링크는 거는 필드)와 노드로 이루어져 있는 연결 리스트

필드 ?

class에 들어있는 변수 --> class는 "필드"와 "메소드"로 이루어져 있다.

 

Array와는 반대의 특성을 가지고 있다.

 

배열과 다르게 LinkedList는 공간상에 랜덤으로 생성된다.

 

LinkedList는 컬렉션에서 List라고 하는 interface class를 이용하여 구현한 것.

--> List list1 = new LinkedList();

 

LinkedList는 배열과는 다른 구조와 다른 연산을 한다.

 

LinkedList의 기본 구조

 

LinkedList는 노드 라는 단위를 사용한다.

노드는 데이터와 다음을 이어주는 링크 필드로 구성 되어 있다.

그래서 데이터를 추가하게 되면 새로운 노드가 만들어지며 다음 데이터와 연결을 시켜주게 된다.

 

여기서 LinkedList를 처음 생성하면 노드 하나가 임의로 생성되는데 이노드에는 데이터는 저장되지 않고

바로 다음에 생성되는 노드와 연결만 하게 된다.

이 노드를 Header(헤더) 라고 하며, LinkedList의 처음 지적임을 인식 하는데에 사용된다.

반대로 맨 마지막 지점은 테일(Tail) 이라고 한다.

 

 

LinkedList의 삽입 연산

 

크게 3가지로 나뉜다.

 

맨 뒤에 삽입(일반적)

중간에 삽입

 

LinkedList의 장점이다.

링크만 노드로 연결시키면 되기 때문에, 시간 손실이 ArrayList보다 훨씬 적다.

앞 뒤로 미는 연산이 없음!

 

맨 앞에 삽입

 

 

LinkedList 제거 연산

 

맨 뒤로 제거

 

중간에 제거

특정 지점의 노드를 제거하고, 링크 필드만 다음 노드로 연결 시키기만 하면 된다.

 

맨 앞에 제거

 

 

LinkedList 탐색 연산

맨 앞의 요소 탐색, 특정 부분 탐색, 맨 뒤 요소 탐색

맨 앞 요소는 header를 이용, 맨 뒤 요소는 tail을 통하여 탐색을 하기 때문에 빠르다.

 

여기서 특정 부분 탐색은 LinkedList의 최대 단점이다.

대상을 탐색하라고 명령이 떨어진다. 

 

탐색을 시작하면 노드의 처음부터 해당 지점까지 해당 지점까지 순차적으로 탐색하게 된다.

 

그 이유는 메모리 공간에서 임의적으로 할당되어 있기 때문에, 링크 필드를 이용하여 

하나하나 찾아다녀야 하기 때문이다. 그래서 탐색은, 배열에 비해서 시간이 많이 걸린다.

 

단순 LinkedList (Singly LinkedList)

데이터, 다음 노드로 가는 링크 필드로 이루어진 노드와 노드로 이루어진 리스트 -> 단방향 탐색

이중 LinkedList (Doubly LinkedList)

데이터, 다음 노드로 가는 링크 필드, 이전 노드로 가는 링크 필드로 이루어진 노드와 노드로 이루어진 리스트 -> 양방향 탐색

자바에서 사용하는 LinkedList는 Doubly LinkedList를 기반으로 한다.

 

 

즉, 다음을 가리키는 링크 필드 next와 이전을 가리키는 링크 필드 prev가 있는 노드로 이루어진 구조이다.

 

두 리스트의 차이점은, 앞으로만 가는가, 앞 뒤로 가는가 의 차이이다.

 

Doubly LinkedList 장점

Singly LinkedList는 단방향 탐색만 가능하기 때문에, 어떤 부분의 탐색 명령이 떨어져도

Header 부분 부터 탐색을 하기 때문에 연산 시간이 오래 걸린다.

 

Doubly LinkedList의 경우, 양방향 탐색이 가능하기 때문에 특정 지점을 탐색하라고 명령을 하게 되면,

이게 Header에 가까운지, Tail에 가까운지 판단을 하게 된다.

그래서 각각의 노드에는 배열처럼 인덱스가 붙게 된다.

 

이 인덱스를 이용하여 어디에 가까운지 판단을 하게 되고,

가까운 부분부터 탐색을 하게 된다.

그래서 Singly LinkedList보다 확실히 빠른 탐색 속도를 보여준다.

 

 

 

LinkedList를 사용하기 위해선 LinkList를 import 해줘야 한다.

그리고 Generic을 이용하여 사용할 형을 정해주면 된다.

 

LinkedList의 주요 메소드

형태	메소드	설명
boolean	add(E e)	e를 리스트의 맨 끝에 추가
void	add(int index, E e)	index위치에 e를 리스트에 추가
boolean	addAll(Collection<? extends E> c)	Collection인 c 전체를 리스트 맨 끝에 추가
boolean	addAll(int index, Collection<? extends E> c)	index 위치에 c 전체를 추가
void	addFirst(E e)	리스트의 시작 부분에 e를 추가
void	addLast(E e)	리스트의 끝부분에 e를 추가
void	clear()	리스트의 내용을 전부 삭제
boolean	contains(Object o)	리스트에 o가 있다면 true, 없으면 false
Iterator<E>	descendingIterator()	역반향으로 순환하는 iterator를 반환
E	get(int index)	index 위치에 값을 반환
E	gerFirst(), getLast()	리스트의 첫 요소, 마지막 요소 반환
int	indexOf(Object o)	o가 있는 인덱스를 반환, 없으면 -1 반환
E	remove()	리스트의 첫 요소를 반환 후 제거
E	remove(int index)	리스트의 index 위치의 요소를 반환 후 제거
E	removeFirst(), removeLast()	리스트의 첫 요소, 마지막 요소를 반환 후 제거
E	set(int index, E element)	index 위치의 값을 element로 변경
int	size()	현 리스트의 크기를 반환
Object[]	toArray()	현재 리스트를 배열로 변환 후 반환

Oracle Java SE documentation 출처

Iterator는 지시자로서 위치를 나타내게 된다.

 

예제

 

출력

 

Iterator는 추 후에 따로 공부를 더 해야겠다. 

 

삽입	제거	탐색
LinkedList	LinkedList	ArrayList

삽입이나 제거에는 LinkedList가 앞서지만, 탐색에서는 ArrayList가 더 좋다.

 

LinkedList는 ArrayList보다 메모리를 더 먹는다.

LinkedList는 앞, 뒤를 나타내는 링크 필드가 추가 되었기 때문이다.