티스토리 뷰
LinkedList(Singly LinkedList)란
LinkedList는 Collection FrameWork란 여러 개의 데이터를 쉽고 효율적으로 관리할 수 있는 표준화된 방법을 제공하는 클래스 중 하나이다. 컬랙션 프레임워크 중 List 인터페이스에 해당된다.
ArrayList는 배열을 토대로 만들어진 List로 데이터를 추가하거나 삭제할 때 크기를 변경할 수 없어서 새롭게 생성해서 copy된 배열을 사용하는 등 "고정된" 배열로 인한 단점이 있었다.
하지만 LinkedList는 이 단점을 해결하기 위해 각 노드가 데이터와 포인터를 가지고 줄줄이 연결되어있는 구조이다. (노드가 서로서로 링크되어있다.)
처음부터 말로 설명을 하면 좀 알아듣기 힘들고 그림으로 먼저 보자.
처음 Header는 시작을 나타내어 Data없이 포인터의 역할만 하고 그 다음 Node부터 보자. Node에는 실제 데이터가 담겨져있는 Data와 List의 그 다음에 담기는 Node의 위치를 가르키는 포인터를 가지고 있다. 그다음 노드도 마찬가지고 계속 같은 방식으로 연결되어있다. 이렇게 연결되어 있기 때문에 (Linked) LinkedList라고 불리는 것이다.
class Node {
Node next; //다음 node의 주소를 저장
Object object; //현재 node의 데이터를 저장
}
Node의 주소를 가지고 서로 연결되어있기 때문에 데이터의 삭제와 추가가 배열과는 달리 매우 간편하다.
삭제를 원하면 그 노드를 삭제하고 이전에 참조하던 주소를 그 다음 node를 참조하게끔 변경하면 되고, 추가를 원하면 새로운 node를 추가하여 앞과 뒤가 참조하던 주소를 그에 맞게 바꾸면 되는 것이다.
이런 LinkedList가 존재하고 있을 때 0x01의 Node가 삭제된다면 0x00 Node가 다음 Node로 참조하고 있던 주소는 0x01이 아니라 0x02가 되어서 연결된 주소를 변경시켜 준다면 삭제가 된다.
추가는 Node와 Node 사이에 새로운 Node를 만들고 삭제에서 했던 것처럼 주소를 이동시켜준다.
0x04의 주소를 가진 Node를 새로 추가를 해주었기 때문에 그 이전의 0x00 Node는 0x04 주소를 참조하고 0x04가 0x00이 참조하던 0x01을 주소를 참조한다.
단, 이 LinkedList는 Singly LinkedList(단일 연결 리스트)라고 불린다. 다음 요소로 이어지는 방향이 단방향이기 때문에 이렇게 지어졌는데 단방향이라 이전 요소로 넘어가는 것이 어려워서 실제 LinkedList는 Doubly LinkedList(이중 연결 리스트)를 사용하며 지금도 이중 연결 리스트를 구현할 것이다.
이중 연결 리스트라고 막 복잡한 것이아니라 Node들에 이전의 Node에 대한 주소를 추가해주는 것에 불과하다.
따라서 우리가 어떠한 node를 찾을 때 굳이 header부터 시작하지 않고 중간의 어떤 node에서 검색을 시작하더라도 검색이 가능하게 변경되었다.
구현
배열때랑 다르게 LinkedList는 Node를 사용한다. 따라서 Node를 자주 사용하게 될 것이기 때문에 Node 클래스를 생성해주도록 한다.
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(E item, Node<E> next, Node<E> prev) {
this.item = item;
this.next = next;
this.prev = prev;
}
}
- E item : Node에 담길 데이터
- Node next : 다음 Node 객체를 가르키는 래퍼런스 변수
- Node prev : 이전 Node 객체를 가르키는 래퍼런스 변수
실제 LinkedList의 Node 클래스를 참고하여서 만들었다. 두가지 의문점이 생길 수 있다.
- 왜 private 접근 지시자인가?
- 왜 static이 붙었는가?
private 접근 지시자의 경우 LinkedList의 내부에서 사용할 객체이기 때문에 외부로 노출되면 보안상의 문제가 발생할 수 있어 private로 접근을 차단하였다.
static은 왜 붙였는가? 는 자세히 알아보려면 내부 클래스에서 static의 사용에 대한 차이를 공부하면 쉽게 알 수 있다. (조만간 빠르게 공부해서 링크달 예정이다.) 간단하게 그 이유를 알아보려면 내부 클래스를 선언할 때 static이 붙게 되면 결국 인스턴스를 생성하는 부분에서 외부 인스턴스 없이 내부 인스턴스를 바로 생성할 수 있을 뿐 기능적인 차이는 없기 때문에 static을 붙여주는데 기능적인 이슈는 더 복잡한 설명이 필요하기 때문에 다음 글 포스팅에 적어보려고 한다.
구현 목록은 다음과 같다. List Interface를 ArrayList와 동일하게 상속받았지만 몇가지 메소드를 추가하였다.
- size()
- isEmpty()
- contains()
- toArray()
- add(), addFirst(), addLast()
- remove(), removeFirst(), removeLast()
- clear()
- get()
- set()
- indexOf(), lastIndexOf()
(코드 가독성을 위해서 javadoc는 지우고 코드를 설명했다. 전체 코드는 github.com/jinyoungchoi95/DataStructure/blob/master/src/DataStructure/List/LinkedList.java에서 확인할 수 있다.)
1. default 세팅
LinkedList 클래스를 생성하고 List 인터페이스를 상속한다.
package DataStructure;
import InterFace.List;
import java.util.NoSuchElementException;
public class LinkedList<E> implements List<E> {
transient Node<E> first;
transient Node<E> last;
private int size = 0;
- first : LinkedList의 가장 처음에 있는 node이다.
- last : LinkedList의 가장 마지막에 있는 nodedlek.
- size : 데이터가 담겨있는 실제 Capacity(용량)이다. LinkedList의 크기를 나타내는 변수이다.
2. Constructor
public LinkedList() {
}
초기 상태는 first node와 last node가 모두 없기 때문에 null로 초기화한다.
3. size()
@Override
public int size() {
return size;
}
LinkedList는 node들이 연결되어 있는 리스트이기 때문에 따로 LinkedList의 크기를 계산할 방법이 없기 때문에 size변수를 인스턴스 변수로 두고 크기를 계산할 때 사용한다.
4. isEmpty()
@Override
public boolean isEmpty() {
return size == 0;
}
LinkedList가 비어있는지를 판단하느나 메소드이다.
size가 0 이라면 true를, 아니라면 false를 반환한다.
5. contains()
@Override
public boolean contains(Object o) {
return (indexOf(o) >= 0) ? true : false;
}
원하는 특정 변수가 LinkedList내에 존재하는지 아닌지를 판별하는 메소드이다.
indexOf()는 이전 ArrayList 구현글에서 indexOf()를 이용하여 contains() 메소드를 재구현하는 것과 마찬가지로 사용하였다. indexOf()는 본 글 하단에 정리해두었으니 아래부분을 먼저 보고 오면 이해하기 쉽다.
indexOf(o)를 통해 원하는 특정 요소의 index값을 구한 후 0보다 크면 해당 요소를 포함하고 있으니 true를, 0보다 작은 -1이 return 되면 포함하지 않아 false를 return 한다.
6. toArray()
@Override
public Object[] toArray() {
Object[] result = new Object[size];
int index = 0;
for (Node<E> x = first; x != null; x = x.next) {
result[index++] = x.item;
}
return result;
}
@Override
public <T> T[] toArray(T[] a) {
if (a.length < size) {
a = (T[]) copy(size, a);
}
int index = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next) {
result[index++] = x.item;
}
if (a.length > size) {
a[size] = null;
}
return a;
}
private Object[] copy(int len, Object[] old) {
Object[] copy = new Object[len];
for (int i = 0; i < len; i++) {
copy[i] = old[i];
}
return copy;
}
LinkedList를 배열의 형태로 반환하는 메소드이다. 이미 생성된 배열에 복사해주는 메소드와 아직 생성되지 않은 배열에 LinkedList가 알아서 배열(Object[])을 생성해서 반환해주는 메소드 두가지가 있다.
toArray() : 생성되지 않은 배열에 복사 - public Object[] toArray()
반환되는 객체의 타입은 LinkedList를 참고하여 그에 맞는 타입 배열로 반환해주어야하기 떄문에 Object[]를 return type으로 받는다. (따라서 해당 메소드에서 Object가 아닌 다른 타입으로 반환을 하려고 하면 Object가 다른 클래스보다 상위에 있기 때문에 에러가 나므로 주의한다.)
import DataStructure.LinkedList;
public class Application {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(3);
list.add(4);
Object[] copyList = list.toArray();
System.out.println("copyList type : " + copyList.getClass().getName());
for(int i=0; i<copyList.length; i++){
System.out.printf("copyList[%d] : ", i);
System.out.println(copyList[i] + ", type : "
+ copyList[i].getClass().getName());
}
}
}
// [출력]
// copyList type : [Ljava.lang.Object;
// copyList[0] : 3, type : java.lang.Integer
// copyList[1] : 4, type : java.lang.Integer
LinkedList의 크기인 size로 배열을 생성한 다음 for문을 돌려 각 index에 들어갈 node의 data를 copy해준 후 배열을 return 해주었다.
배열을 그대로 copy하던 ArrayList와 달리 node가 연결되어있어 다음 node를 하나하나 추적해서 연결시켜준다.
toArray() : 생성된 배열에 복사
이미 생성된 배열의 경우 제한된 크기가 생겨져 버리기 때문에 LinkedList의 크기에 맞게 배열을 새로 만들고 끝냈던 이전 메소드와는 다르게 몇가지 과정이 추가된다.
LinkedList의 크기가 주어진 배열보다 클 경우 생성되지 않은 배열에 복사하는 동작과 동일하다. 넣어야하는 LinkedList의 size보다 기존 배열이 작기때문에 기존 배열을 늘려서 LinkedList를 copy한 배열을 return해야하기 때문이다.
단, 기존의 배열이 더 큰 경우 "기존 배열의 크기가 좀 더 크기 때문에 LinkedList의 size만큼만 넣어준다"로 복사를 해주는데, ArrayList와 마찬가지로 LinkedList 또한 배열 크기가 size보다 클 때 배열의 size에 null 값을 넣어준다.
public class Application {
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<>();
list.add(3);
list.add(4);
Integer[] array = new Integer[]{1,2,3,4,5};
array = list.toArray(array);
System.out.println(Arrays.toString(array));
}
}
// [출력]
// [3, 4, null, 4, 5]
분명 [1,2,3,4,5] 배열에 [3,4]의 LinkedList를 복사했으니 [3,4,3,4,5]가 나온다고 생각하겠지만 LinkedList를 복사해주었기 때문에 복사된 배열에 List의 길이를 표기한다는 의미에서 null값을 넣은 것으로 java에서 toArray() 메소드에서 정한 약속이라고 보면된다. 따라서 LinkedList의 크기보다 더 큰 배열에 LinkedList를 복사할 경우 null 값이 들어오는 것에 대한 대처를 하여야 한다.
(참고 내용 https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html)
7. add(), addFirst(), addLast()
add() 메소드는 List의 가장 마지막에 node를 추가하는 메소드, 가장 처음에 node를 추가하는 메소드, List의 특정 위치에 node를 추가하는 메소드가 있다. 차례로 알아보자
add(), addLast() : List의 가장 마지막에 node 추가
@Override
public boolean add(E e) {
linkLast(e);
return true;
}
public void addLast(E e) {
linkLast(e);
}
private void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null) {
first = newNode;
} else {
l.next = newNode;
}
size++;
}
List의 가장 마지막 node에 추가하게 되었을 때 그 node가 가져야할 값은 이전 node, value, 다음 node(null)이다.
이전 node는 당연히 List의 마지막에 연결하는 것이기 때문에 List의 가장 마지막에 있는 last node이다. value는 매개변수로 받은 값을 넣으면 된다.
그럼 다음 node는 당연히 null이 들어간다. 지금 추가하는 node가 가장 마지막 node가 되기 때문에 이 다음 node는 없는 것이므로 null이 되는 것이다.
그림을 보면 기존의 Last는 다음 node로 null을 가지고 있었지만 뒤에 새로 node가 생겨남으로 new node를 다음 node(next)로 가지게 되었고 new node는 Last가 되며 이전 Last를 이전 node(prev)로 가지게 되는 것이다.
메소드는 그림에서 보여준 일련의 과정을 그대로 코드로 옮긴 것으로 주의할 것은 if문에 있다. 만약 LinkedList가 비어있을 때를 고려해야한다. 만약 LinkedList가 비어있다면 당연히 last를 받아온 상수 l은 null 일 것이다. LinkedList가 비어있으면 first와 last는 둘다 null로 없는 값이기 때문이다. 따라서 l==null일 때는 현재 들어온 새로운 node를 first로도 지정해준다. 그게 아닐 경우 위 그림에서 last의 next 값을 null 대신 새로운 node로 연결해준다.
단순하게 정리를 하면
- LinkedList가 비어있어 first, last가 없을 경우 새로 들어온 node가 first, last가 된다.
- 아닌 경우 last뒤에 새로 들어온 node가 위치하여 이 node가 last가 된다.
로 정리할 수 있다.
addLast()와 add()의 기능은 같지만 return type이 다르며 add는 boolean으로 List에 추가했을 경우 true를 return한다.
addFirst() : List의 가장 처음에 node 추가
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node(null, e, f);
first = newNode;
if (f == null) {
last = newNode;
} else {
f.prev = newNode;
}
size++;
}
addLast()와 반대로 생각하면 된다. List의 가장 처음 node를 추가하게 되었을 때 그 node가 가져야할 값은 이전 node(null), value, 다음 node이다.
node를 추가하는 과정은 addLast()에서 해봤으니 바로 그림으로 넘어간다.
기존의 first의 앞에 새로운 node를 추가해주는 것이기 때문에 기존의 first에서 참조하던 prev(null)은 new node가 되고, new node의 next는 기존의 first가 된다. 그 후 새로운 node가 LinkedList의 완전한 first가 되게 된다.
단, 마찬가지로 기존의 first node가 null인 경우 LinkedList가 비어있다는 뜻이기 때문에 new node를 first 뿐만 아니라 last로 지정해준다.
- LinkedList가 비어있어 first, last가 없을 경우 새로 들어온 node가 first, last가 된다.
- 아닌 경우 first 앞에 새로 들어온 node가 위치하여 이 node가 first가 된다.
add() : 특정 index에 node 추가
@Override
public void add(int index, E element) {
rangeCheckForAdd(index);
if (index == size) {
linkLast(element);
} else {
linkInIndex(element, node(index));
}
}
private void linkInIndex(E e, Node<E> input) {
final Node<E> prev = input.prev;
final Node<E> newNode = new Node(prev, e, input);
prev = newNode;
if (prev == null) {
first = newNode;
} else {
prev.next = newNode;
}
size++;
}
private Node<E> node(int index) {
Node<E> x;
if (index < (size >> 1)) {
x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
} else {
x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
}
return x;
}
private void rangeCheckForAdd(int index) {
if (index < 0 || this.size < index) {
throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + this.size);
}
}
먼저 index가 LinkedList가 가지고 있는 범위를 넘어서는지 예외처리를 한다.
그 후 두 가지로 나뉘는데 원하는 index가 LinkedList의 크기와 같은 경우 가장 마지막에 추가하는 것이기 때문에 addLast()와 동일한 메소드를 사용해준다.
특정 Index에 원하는 node를 추가하기 위해서는 먼저 특정 Index 위치에 있는 node를 찾아야 한다. for문으로 node의 next를 넘겨받아서 그 index가 나올 때까지 돌린다. 단, Singly LinkedList와는 다른 차이점이 지금 Doubly LinkedList에서 보인다.
Singly LinkedList의 단점이 무엇인가라고 하면 node가 연결되어 있는 방향이 단방향이기 때문에 원하는 node를 찾으려면 처음부터 끝까지 for문을 다돌려야해서 성능상 손해를 본다. 하지만 Doubly LinkedList는 앞, 뒤 어느곳에서 시작하든 양방향성을 가지기 때문에 index가 전체 size에서 반틈보다 작을 때 (index < (size>>1)) 앞에서부터 node를 착고 반틈보다 클 때 else 뒤에서부터 node를 찾게 되는 것이다.
그 후의 과정은 addFirst()와 동일하다. 원하는 위치의 node 뒤에 새로운 node를 추가하는 것으로 index node가 first였을 경우 새로운 node가 자연스럽게 first가 되고, 아닌 경우 이전 node의 next값이 새로운 node가 된다.
8. remove(), removeFirst(), removeLast()
remove() 메소드도 add() 메소드와 기본 메커니즘은 비슷하기 때문에 이제 이해하기 쉬울 것이다.
removeFirst()
public E removeFirst() {
if (first == null) {
throw new NoSuchElementException();
}
return unlinkFirst();
}
private E unlinkFirst() {
final E item = first.item;
final Node<E> next = first.next;
first = next;
if (first == null) {
last = null;
} else {
first.prev = null;
}
size--;
return item;
}
가장 첫번째 first node를 제거하는 메소드이다. first node가 없다면 제거할 element가 없기 때문에 예외처리를 해준다.
기존의 first node 자리에 first.next node를 대치해주며 변경된 first가 null인 경우에는 현재 LinkedList의 크기가 1밖에 없어 first가 null이 되면 LinkedList의 크기가 0이 되므로 last까지 같이 null로 초기화하여야한다.
removeLast()
public E removeLast() {
if (last == null) {
throw new NoSuchElementException();
}
return unlinkLast();
}
private E unlinkLast() {
final E item = last.item;
final Node<E> prev = last.prev;
last = prev;
if (last == null) {
first = null;
} else {
last.next = null;
}
size--;
return item;
}
가장 마지막 last node를 제거하는 메소드이다. last node가 없다면 제거할 element가 없기 때문에 예외처리를 해준다.
기존의 last node 자리에 last.prev node를 대치해주며 변경된 last가 null인 경우에는 현재 LinkedList의 크기가 1밖에 없어 last가 null이 되면 LinkedList의 크기가 0이 되므로 first까지 같이 null로 초기화하여야한다.
remove()
@Override
public E remove(int index) {
rangeCheck(index);
return unlink(node(index));
}
private E unlink(Node<E> x) {
final E item = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
return item;
}
조금 복잡할 수도 있지만 지금까지 해왔던 add()와 removeFirst(), removeLast()의 연장선이라고 보면 쉽다.
말로 설명하면 장황해질 것 같으니 그림부터 보자!
목적은 본 LinkedList에서 0x01 node를 제거하는 것이다. removeFirst()와 removeLast()를 복합적으로 생각해보면 0x01 node 객체의 모든 값을 null로 처리하여 GC가 해당 객체를 Heap 영역에서 알아서 처리하도록 초기화하고, 0x00과 0x02를 연결해주면된다. 0x00의 next node를 0x01이 아닌 0x02로, 0x02의 prev node를 0x01이 아닌 0x00으로 변경한다.
코드로 보면 어려워보이는데 막상 제거되는 과정을 보면 그렇게 복잡하지않다. 여기서 지워지는 Node(여기서는 0x01)이 first node 이거나 last node일 경우에만 주의해서 if문을 작성하면 된다.
9. clear()
@Override
public void clear() {
for (Node<E> x = first; x != null; ) {
Node<E> next = x.next;
x.item = null;
x.next = null;
x.prev = null;
x = next;
}
first = last = null;
size = 0;
}
List의 모든 요소를 비우는 메소드이다.
for문으로 LinkedList의 모든 node를 돌며 각 node의 인스턴스 변수들을 null로 초기화해준다. (first, last도 null로 처리) null로 처리를 하는 이유는 GC가 JVM의 Heap 영역에 들어있는 인스턴스 변수를 본인이 알아서 처리를 해주기 때문에 null로 초기화를 해두었을 때 GC가 판단하여 Heap 영역을 관리해 준다.
LinkedList의 값이 비었으므로 size를 0으로 초기화 해준다.
10. get()
@Override
public E get(int index) {
rangeCheck(index);
return node(index).item;
}
private Node<E> node(int index) {
Node<E> x;
if (index < (size >> 1)) {
x = first;
for (int i = 0; i < index; i++) {
x = x.next;
}
} else {
x = last;
for (int i = size - 1; i > index; i--) {
x = x.prev;
}
}
return x;
}
원하는 위치에 있는 객체의 item을 가져오는 메소드이다.
먼저 index가 LinkedList 내에 허용되는 index인지 확인하는 예외처리를 한다.
위에서 사용했던 index를 받았을 때 node객체를 return해주는 node 메소드를 사용한다.
그 후 찾은 node객체의 item을 반환한다.
11. set()
@Override
public E set(int index, E element) {
rangeCheck(index);
Node<E> x = node(index);
E oldValue = x.item;
x.item = element;
return oldValue;
}
LinkedList의 원하는 위치에 있는 객체에 원하는 item을 삽입하는 메소드이다.
get()메소드와 마찬가지로 node 메소드를 이용하여 원하는 객체를 찾고 그 객체의 item을 입력받은 element로 변경해준다. 메소드의 return 값은 이전에 index에 위치해있던 변수이므로 E oldValue에 미리 저장하여 return 한다.
12. indexOf(), lastIndexOf()
@Override
public int indexOf(Object o) {
int index = 0;
if (o == null) {
for (Node<E> x = first; x != null; x = x.next, index++) {
if (x.item == null) return index;
}
} else {
for (Node<E> x = first; x != null; x = x.next, index++) {
if (o.equals(x.item)) return index;
}
}
return -1;
}
@Override
public int lastIndexOf(Object o) {
int index = size - 1;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev, index--) {
if (x.item == null) return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev, index--) {
if (o.equals(x.item)) return index;
}
}
return -1;
}
LinkedList에서 원하는 특정 item이 위치하는 node를 찾는 메소드이다. 단순히 다음 next나 이전 prev로 계속 node를 연결해서 해당 item을 가지는 node가 나올 때 까지 for문을 돌린다.
ArrayList때와 마찬가지로 == 연산자를 사용할 때 주의해야한다. null은 ==를 사용해도되지만 객체를 비교하는 경우 .equals()를 통해서 정확하게 객 비교를 하여야 한다.
찾았을 경우 해당 index를, 못찾았을 경우 -1을 리턴한다.
앞에서도 말했지만 전체 코드는 깃허브에 전부 저장을 해두었습니다.
최대한 공식문서와 실제 class 파일을 참고하여 만들었지만 혹시 모를 이탈자나 잘못된 부분은 댓글로 피드백 부탁드립니다.
[참고 자료]
https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html (oracle java docs)
'자료구조' 카테고리의 다른 글
| [JAVA] Collection Interface/ add()와 offer() 차이 (1) | 2021.04.21 |
|---|---|
| [JAVA] Deque 직접 구현하기 (0) | 2021.04.20 |
| [JAVA] Queue 직접 구현하기 (1) | 2021.04.20 |
| [JAVA] Stack 직접 구현하기 (0) | 2021.04.16 |
| [JAVA] ArrayList 직접 구현하기 (2) | 2021.03.19 |
- Total
- Today
- Yesterday