나는 언제 LinkedList를 사용했는가? 데이터를 주로 앞에서 삽입하는 경우 즉 queue의 자료구조가 필요했다면 사용한 것 같다.
linked 연결되 있다는 소리이다. 여기에 는 그렇다면 그래프, 트리 도 포함되어야 마땅하지 않겠는가? 이 두 개의 자료구조 또한 연결된 구조다. 다만 이번 챕터에서 분석하고 성능측정 해볼 것은 다음의 하나의 노드만 포인팅 하는 자료구조를 공부해볼 것이다.
연결 자료 구조는 데이터 하나를 크게 노드라는 단위로 부르고 있으며 노드 안에는 하나의 데이터가 들어있고 다음 노드를 포인팅 하는 주소값이 들어가 있다.
바로 구현해 보자.
생성자 몇 개 와 toString을 만들어 나의 편의성을 위해 위와 같이 작성했다. 이번에도 역시 숫자의 데이터 값만 받아서 노드를 구상할 생각이다.
지난번에 사용한 인터페이스 그냥 그대로 가져다 사용해도 될 것 같다고 생각한다. 사실 명확하게 떠오르는 생각 이 없다..... LinkedList 본연의 기능보다 오히려 Queue 형태의 자료구조로 더 많이 사용했던 것 같다.
생각보다 사용한 함수들 이 많이 있어서 일단 작성했다. (API DOC을 참고해서 작성)
public interface LinkedListInterface {
void add(int index,int number);
boolean add(int number);
void addFirst(int number);
void addLast(int number);
boolean contains(int number);
int get(int index);
int getFirst();
int getLast();
int indexOf(int number);
boolean offer(int number);
boolean offerFirst(int number);
boolean offerLast(int number);
int peek();
int peekFirst();
int peekLast();
int poll();
int pollFirst();
int pollLast();
int pop();
void push(int number);
int remove();
int remove(int index,int number);
int removeFirst();
int removeLast();
int set(int index,int number);
int size();
}구현
package datastructure.myLinkedList;
import java.util.LinkedList;
public class GuiwooLinkedList implements LinkedListInterface {
private int total;
private GuiwooNode first;
private GuiwooNode last;
public GuiwooLinkedList() {
this.total = 0;
this.first = null;
this.last = null;
}
@Override
public void add(int index, int number) {
if(index >= this.size()) throw new IndexOutOfBoundsException();
if(this.size() == 0 || this.size() == index+1){
this.add(number);
return;
}
if(index == 0){
first = new GuiwooNode(number,first);
}else{
int count = 0;
GuiwooNode current = this.first;
GuiwooNode previous = this.first;
while(count < index){
previous = current;
current = current.next;
count++;
}
previous.next = new GuiwooNode(number,current);
}
total++;
}
@Override
public boolean add(int number) {
if(first == null){
first = new GuiwooNode(number);
first.next = first;
last = first;
}else{
GuiwooNode next = new GuiwooNode(number);
last.next = next;
last = next;
}
total++;
return true;
}
@Override
public void addFirst(int number) {
if(this.size() == 0){
this.add(number);
}else{
first = new GuiwooNode(number,first);
}
}
@Override
public void addLast(int number) {
this.add(number);
}
@Override
public boolean contains(int number) {
return this.indexOf(number) >= 0;
}
@Override
public int get(int index) {
if(index >= this.size()) throw new IndexOutOfBoundsException();
GuiwooNode current = this.first;
int cnt = 0;
while(cnt < index){
current = current.next;
cnt++;
}
return current.data;
}
@Override
public int getFirst() {
if(first == null) throw new NullPointerException();
return first.data;
}
@Override
public int getLast() {
if(first == null) throw new NullPointerException();
return last.data;
}
@Override
public int indexOf(int number) {
GuiwooNode current = this.first;
int cnt = 0;
while(current != null){
if(current.data == number) return cnt;
cnt++;
current = current.next;
}
return -1;
}
@Override
public boolean offer(int number) {
try{
return this.add(number);
}catch (Exception e){
return false;
}
}
@Override
public boolean offerFirst(int number) {
try{
this.addFirst(number);
return true;
}catch (Exception e){
return false;
}
}
@Override
public boolean offerLast(int number) {
try{
this.addLast(number);
return true;
}catch (Exception e){
return false;
}
}
@Override
public int peek() {
return this.getFirst();
}
@Override
public int peekFirst() {
return this.getFirst();
}
@Override
public int peekLast() {
return this.getLast();
}
@Override
public int poll() {
if(first == null) throw new NullPointerException();
int value = first.data;
first = first.next;
return value;
}
@Override
public int pollFirst() {
return this.poll();
}
@Override
public int pollLast() {
GuiwooNode current = first;
GuiwooNode previous = first;
while(true){
if(current.next == null) break;
previous = current;
current = current.next;
}
previous.next = null;
return current.data;
}
@Override
public int pop() {
return this.pollLast();
}
@Override
public void push(int number) {
this.add(number);
}
@Override
public int remove() {
return this.pollLast();
}
@Override
public int remove(int index) {
if(index >= this.size()) throw new IndexOutOfBoundsException();
if(index == 0) return this.poll();
else if(index+1 == this.size()){
return this.pollLast();
}else{
int cnt = 0;
GuiwooNode current = first;
GuiwooNode previous = first;
while(cnt < index){
cnt++;
previous = current;
current = current.next;
}
previous.next = current.next;
return current.data;
}
}
@Override
public int removeFirst() {
return this.pollFirst();
}
@Override
public int removeLast() {
return this.pollLast();
}
@Override
public int set(int index, int number) {
if(index >= this.size()) throw new IndexOutOfBoundsException();
GuiwooNode current = first;
int count = 0;
while(count <index){
if(current != null) current = current.next;
count++;
}
current.data = number;
return number;
}
@Override
public int size() {
return this.total;
}
}테스트 코드
package datastructure.myLinkedList;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.BeforeAll;
import org.junit.jupiter.api.BeforeEach;
import org.junit.jupiter.api.Test;
import static org.junit.jupiter.api.Assertions.*;
public class GuiwooLinkedListTest {
private GuiwooLinkedList gll;
private int listSize = 10;
@BeforeEach
void init(){
gll = new GuiwooLinkedList();
for(int i=1;i<=listSize;i++){
gll.add(i);
}
}
@Test
void addBasic(){
int i = gll.indexOf(10);
assertEquals(9,i);
}
@Test
void contains(){
boolean contains = gll.contains(100);
assertFalse(contains);
}
@Test
void sizeCheck() throws Exception{
int size = gll.size();
assertEquals(listSize,size );
}
@Test
void addNumberByIndex() throws Exception{
gll.add(0,100);
int i = gll.indexOf(100);
// 맨 앞에 추가할때
assertEquals(0,i);
// 가운데 추가할때
gll.add(5,500);
int i1 = gll.indexOf(500);
assertEquals(5,i1);
assertEquals(listSize+2,gll.size());
}
@Test
void addFirst(){
gll.addFirst(10000);
int i = gll.indexOf(10000);
assertEquals(i,0);
}
@Test
void addLast() throws Exception{
gll.add(20000);
int i = gll.indexOf(20000);
assertTrue(gll.contains(20000));
assertEquals(listSize,i);
assertEquals(listSize+1,gll.size());
}
@Test
void getByIndex() throws Exception{
int i = gll.get(0);
assertEquals(1,i);
int i1 = gll.get(9);
assertEquals(10,i1);
}
@Test
void getFirst() throws Exception{
int first = gll.getFirst();
assertEquals(1,first);
}
@Test
void getLast() throws Exception{
int last = gll.getLast();
assertEquals(10,last);
}
@Test
void peek() throws Exception{
int peek = gll.peek();
assertEquals(1,peek);
int i = gll.peekFirst();
assertEquals(1,peek);
int i1 = gll.peekLast();
assertEquals(10,i1);
}
@Test
void poll() throws Exception{
for(int i=1;i<=listSize;i++){
int poll = gll.poll();
assertEquals(poll,i);
}
}
@Test
void pollLast () throws Exception{
int i = gll.pollLast();
assertEquals(10,i);
}
@Test
void removeByIndex () throws Exception{
gll.remove(5);
int i = gll.indexOf(6);
int i1 = gll.get(5);
assertEquals(i,-1);
assertEquals(i1,7);
}
@Test
void set() throws Exception{
gll.set(9,1000);
int i = gll.indexOf(1000);
assertEquals(9,i);
}
}
어제 와는 다르게 apiDoc을 보고 작성했으니 실질적인 비교를 해보자.
먼저 클래스 작성자의 설명을 읽어보자.
doubly-linked list라는 표현을 쓴다. 이중연결 리스트?라고 해석이 되는데 음 그러면 노드의 선언이 잘못되었다.
노드 내부적으로 필드가 하나 더 추가되어 앞뒤로 탐색이 가능해야 한다. 단방향 리스트 가 되어버린 내 구현체는 반쪽 짜리였다.
어쩐지 함수를 작성할 때마다 매번 역방향 탐색 이 있다면 적어도 50% 이상의 성능향상 이 있다고 생각되던 참이던데 참...
마저 읽다 보면 arrayList와 동일하게 이 클래스도 동기화 예약어를 사용하지 않는다.
다중 스레드 환경에서 비동기적 수행이 필요하다면 아래와 같은 방식을 권장한다.
Collections.synchronizedList(new LinkedList(...));읽다 보면 재미있는 설명과 예외가 있다. ConcurrentModificationException 전 회사 다닐 때 마주했던 에러였다.
언제 발생하는가? 리스트를 순회하면서 데이터 수정 을 하게 되면 마주하게 되는 에러이다.
modCount를 비교하면서 순회하게 되는데 이때 modCount 순회와 modCount의 값을 비교하면서 돌게 되는데 이때 숫자가 맞지 않다면 위와 같은 에러를 뱉어낸다. 한 번씩 고의로 에러를 내보면 어떤 의미인지 이해하기 쉽다.
listIterator 의해 수행되는 반복자는 빠르게 위 예외를 터트린다고 한다. 최대한 빠르게 위 에러를 터트리는데, 클래스 작성자는 이 예외에 의존해 프로그램을 작성하지 말라고 말한다. 오직 버그를 확인하기 위해 확인하라고 한다.
즉 동기화되지 않은 동시 수정이 있는 겨우 위와 같은 에러를 빠르게 터트려 주어 사전에 방지해주는 함수 설계가 되어 있지 않을까라고 생각한다. modCount 가 여기서 말하는 빠르게 터트리는 트리거 일 것 같은데 차근차근 함수를 살펴보자.
- 특정 인덱스에 원하는 값을 넣어주는 함수이다
- 나의 구현 : 인덱스 가 현재 사이즈 보다 크거나 같은 경우 예외를 던지고, 제일 앞에 추가할 때 뒤에 추가할 때의 분기를 나누어 주었고 , 사이즈에 따른 분기도 나누어 주었다.
- 총 3개의 함수를 호출한다. (checkPositionIndex, linkLast, linkBefore)
- checkPositionIndex => 말 그대로 들어온 인덱스의 범위를 확인하는 함수이다.
- linkLast => index와 사이즈가 같은 경우 분기를 나눈다. 함수 내부적으로 총 개수에 따라 다시 분기를 나누고 first last 그리고 size를 업데이트해준다.
- linkBefore => 말 그대로 가운데 끼여 주는 함수이다. 확실히 previous 포인터 가 있으니깐 함수가 훨씬 간단한다.
o(n) 만큼 의 시간이 걸릴 것으로 보인다. for loop에 의해 분기를 돌아 index까지 current와 previous 업데이트가 필요하기 때문이다.
node(index)의 함수가 따로 있는데 이건 인덱스에 따른 노드를 반환해주는 함수이다.
1000줄 이 넘어가는 클래스이다 보니 클래스 작성자도 귀찮았는지 x라는 변수를 선언해서 리턴해준다. ㅋㅋ
클린코드 읽다 보면 변수명에 대해 한 챕터를 사용할 정도로 중요하게 생각하는 거 같은데 작자 가 중간중간 자바 의 몇몇 클래스에 대해 혹평을 내리고는 하는데 이런 것 들도 그의 마음에 들지 않았을 것으로 생각된다.ㅎㅎ
다만 이 이렇게 previous와 next를 동시에 가지고 있다면 total 기준으로 반으로 나눠 가까운 쪽에서 시작한다면 최소 내가 작성한 코드보다 빠를 것으로 예상된다.
add(E e)
- 가장 끝 쪽에 e를 추가해주는 함수이다.
- 나의 구현 : 총 total의 숫자를 증가시켜 주고, 현재 노드가 없는 경우만 판별해 분기를 나눠 주었다. null이라면 first와 tail 모두 동일한 노드이기 때문에 이렇게 분기를 나눠주었다.
- 위에서 사용한 linkLast(e)에 그냥 return true이다.
- 사실 인터페이스 작성하고 클래스 구현을 하면서 이 함수에서 boolean을 리턴하면서 얻게 되는 이득이 뭔지 고민을 많이 해봤다. 도대체 어떤 경우에 false 리턴하는지 몰랐는데... 그냥 여기 클래스 작성자도 true로 박아놨다. ㅎㅎ.. 고민 한 시간이 아깝다...
o(1)의 시간이 걸릴 것으로 예상된다. 왜? tail을 직접적으로 필드 내에 가지고 있기 때문에 바로바로 접근이 가능하다. 고민의 여지없이 상수 시간이다.
addFirst(E e)
- 이번에는 가장 앞쪽에 e를 추가해주는 함수이다.
- 0인 사이즈에 따라 분기를 나눠 위에서 작성한 add(E e)를 이용해 추가해주거나 head를 교체해주거나 단순하다.
- modCount와 size를 증가시켜 주고, linkFirst라는 새로운 함수가 있는데 내가 작성한 것 과 다를 바 없다.
- o(1)의 시간이 소요된다 이유는 위와 동일하다.
addLast(E e)
- 나의 구현 : 끝에 추가하나 add를 이용해서 마지막에 추가하나 별차이를 모르겠다 실제로도 그냥 add 함수를 내부적으로 구현했다.
- add와 동일하게 구현되어 있다 단 차이점이라면 반환값의 유무 정도?
- o(1) add 함수 자체를 들고 와서 사용하기 때문에 이렇게 정했다.
contains(E e)
- e 가 list 안에 존재하는 여부를 반환해주는 함수이다.
- 나의 구현 : 지난번 ArrayList에서 했듯이 indexOf를 이용해 -1을 리턴하면 false를 리턴하는 함수를 작성했다.
- 나의 구현과 동일하게 작성되어 있다. indexOf를 이용해 반환한다.
- indexOf는 loop를 이용해 리스트를 순회하기 때문에 o(n) 시간 복잡도를 소요한다.
get(int index)
- 연결 리스트 이더라도 리스트 본연의 get 이 있어야 한다. index에 따른 값을 반환한다.
- 나의 구현 : index 범위를 확인 후 하나의 currentNode와 count를 지정해 count 가 index에 도달할 때까지 루프를 돈다.
- 확실히 pervious 가 있으니깐 위에서 내가 언급했듯이 index와 전체 크기를 비교해 반 이하라면 front에서 이상이라면 rear로부터 시작한다.
- o(n)이라고 해야 할지 o(lonN) 이라고 해야할지 잘 모르겠다. 어쨌든 o(n) 보다는 빠르다는 생각이 든다. o(1) 보다는 느리지만 o(n) 보다는 빠르기 때문에 o(logN)이라고 생각한다.
getFirst()
- 함수명 그대로 당연히 첫 번째 Element를 반환한다.
- 나의 구현 : Frist에 해당하는 포인터는 객체 내부에 존재하기 때문에 바로 조회 가능하다.
- null 체크 이후 바로 나와 유사하게 리턴을 때려주는 모습이다.
- 의심 여지없이 o(1) 시간복잡도를 가진다.
getLast()
- 함수명 그대로 마지막 Element를 반환한다.
- 나의 구현 : First와 동일하게 Last 즉 tail 노드 도 가지고 있기 때문에 바로 조회 가능하다.
- 위와 동일하다.
- o(1) 시간 복잡도
indexOf(E e)
- 주어진 오브젝트의 인덱스를 반환하는 함수이다 없다면 -1을 반환하기 때문에 contains에서 활용된다.
- 나의 구현 : 사실 이 함수를 제일 먼저 구현했다. testCode에서 확인을 위해서는 add와 확인 이 필요하기 때문에 먼저 작성했다,
단순하게 while을 이용해 동일한 오브젝트를 만날 때까지 돌린다.
- 나와 동일하게 반복문 한 번의 순회를 통해 동일한 값을 찾아낸다. 다만 null 인 경우 의 분기를 나눠준다.
- for 문 자체를 정말 깔끔하게 사용했다. 아래와 같은 방식으로 사용했다. 중간 x!= null 이 인상적이다.
for(Node<E> x = first; x != null; x = x.next){- 한 번의 순회를 모두 거쳐야 하기 때문에 o(n) 시간복잡도를 의미한다.
// 여기부터 Queue Opertaion이라고 명시되어 있다.
offer(E e)
- 마지막에 요소를 추가한다. 사실 add와 이것의 차이를 둬서 구분하는 이유를 모르겠다 둘 다 동일한 반환값에 동일한 기능을 하는데
- 찾아보니 인터페이스(Queue)의 기능 구현을 위해 작성이 된 코드이다. ㅋㅋ....
- 자바 구현 자체도 return add(E e)이다.
- offerFirst, offerLast 전부 동일한 사유이다.
peek()
- 가장 앞에 있는 값을 보여준다. null 체크 후 first의 값을 반환한다.
- peekFirst(), peekLast() 동일하다.
poll()
- 앞에서부터 이번에는 뽑아간다. 즉 인덱스 및 총사이즈가 변경되는 함수이다.
- 나의 구현 : null check 이후 first를 다음 first 로 바꿔주고 바꾸는 과정 중 잠시 데이터를 가지고 있다 리턴한다.
- first 를 받아서 unlinkFirst 함수를 실행한다. 이 함수는 first 자체를 null로 바꿔주는 코드가 있다. 왜? 가비지컬렉션에 도움이 되기 위해 이 코드를 작성했다고 되어있다. 와... 이런 부분까지 신경 쓰는지 몰랐다.
- 이 함수에서는 놓친 부분이 많다. null을 이용해 gc에 도움을 주고, total의 수도 줄여주지 않았다. 이런 실수를 줄여야 하는데 후...
- o(1) 시간복잡도라고 믿어 의심치 않는다.
- pollFirst(), pollLast() 도 동일하게 구현되어 있다. pollLast()는 unlinkLast 함수이고 first와 동일한 로직이다.
pop(), push()
- stack을 표현하기 위해서 작성된 함수이다. 각각 addFirst , removeFirst 등의 함수를 각각호출한다.
remove(int index)
- 나의 구현 : index 가 0 인경우 혹은 size와 같은 경우는 바로 리턴을 해주는 최적화를 적용했다.
함수 내부적으로 count와 previous, current 3개 의 변수를 두어 index까지 조회하고 previous.next = current.next를 이용해 지워 주었다. 이렇게 보니 이렇게 되면 gc에서 삭제된 current를 즉각 회수하지 않는다. 계속 힙메모리를 차지하고 있는 반쪽 자리이다.
- 위에서 한번 언급한 node(index)를 이용해 해당 노드를 가져온다. 이렇게 해도 되는 이유는? 필드 내부적으로 전 그리고 다음 노드가 있기에 가능한 방법이다. unlink에서 역시나 삭제된 노드는 바로 null 처리를 통해 메모리 최적화가 진행되어 있다.
removeFirst(), removeLast() 모두 위에 언급한 unlinkFirst, unlinkLast를 이용해 사용된다.
사실 LinkedList 클래스 내부적으로 이 위의 함수들의 구현된 사항은 몇 줄 되지 않는다.
list-iterator, 직렬화, clone을 위한 코드가 400줄 이 넘는다. 그중 list-iterator에 대해 말하고 싶다.
위에서 언급한 ConcurrentModificationException 은 이 친구가 뱉어준다.
Iterator 가 만들어진 이후 remove 혹은 add를 이용해 수정을 한다면? 저 위의 에러가 뱉어진다.
checkForComodification을 이용해 modCount와 expectedModCOunt를 비교해 빠르게 에러를 뱉어준다. 위에서 add, remove 함수에서 전체 개수 외에 modCount 도 같이 체크해준 이유가 된다.
LinkedList , ArrayList 내가 전에 사용하던 느낌이 맞다. 두 클래스 모두 다중 스레드에서는 안전하지 않는다.
무언가 를 추가하고, get()의 사용빈도가 적다? 여지없이 LinkedList를
그게 아닌 get(), set()의 빈도가 높다면 ArrayList의 선택이 타당하다.
CS 적으로 생각해 보자.
ArrayList는 하나의 긴 띠 안에 자료들이 오와 열을 맞춰 정렬되어 있다. 그러나 LinkedList는? 여기저기 흩뿌려져 있다. 하드웨어 적으로 이는 낭비를 의미할 수도 있다.
다시 말해 속도의 측면 만 이 아닌 공간적 측면을 보더라도 어느 정도의 cost 가 각각 있다.
Think Data Structures 책에서는 다음과 같이 언급한다.
1. 응용프로그램 의 실행 시간이 중요하다.
2. 응용 프로그램의 실행시간이 선택한 자료구조에 의존한다.
3. 증가 차수에 따라 어느 자료구조가 나은지 실제로 예측할 수 있을 만큼 문제크기가 충분히 크다.
즉 작업하는 리스트 가 어마무시하게 크지 않다면 기대하는 성능을 얻기 어려울지도 모른다. 작은 문제에서는 이차 알고리즘 이 선형 알고리즘 보다 빠르기도 하고 선형 알고리즘이 상수시간 보다 빠르기도 하다.
LinkedList를 공부하면서 예전에 잠깐 읽은 블록체인 이 생각난다. 블록체인 또한 현재의 해쉬값 에는 전 해쉬 값이 포함되기 때문에 생각이 났다. 이런 기술에서도 이런 자료구조 가 접목 되어 있는 부분이 있어 자료구조 의 명확한 이해가 보다 중요해지는 거 같다.
그리고 최근 읽은 블로그 글이 생각난다. C++, C 등의 언어가 다시 떠오르고 있다고 한다 왜? 클라우드 서비스를 이용하는 최신 서비스 들은 메모리의 성능, 하드웨어의 사용 은 즉각적인 비용으로 청구되기 때문에 이에 대한 최적화를 위해 migration 진행하는 곳도 많다는 Medium 블로그 글을 읽은 적이 있다.
GC의 최적화 보다 메모리 관리를 직접 하는이 언어 들은 어느 정도 의 큰 데이터를 다뤄야 다른 언어에서 넘어갈 만큼 의 효율이 있는지도 궁금하다. 책에서는 어느정도 큰 데이터를 다루지 않는다면 유의미한 성능을 얻기 어렵다고 말한다. 그렇다면 다시 말해 그만큼 jvm 메모리에서 들고 있어줘야 한다는 소리인데. 이런 경험을 해보려면 도대체 얼마나 많은 양의 리스트를 들고 있어야 하는지 느낌도 없다.
이번 공부를 통해서 나름의 ArrayList와 LinkedList의 사용의 내 나름의 기준이 세워졌다. 전에 생각하던 이유에 몇 개 더 추가되진 않은 것 같지만 이렇게 java의 코드를 이렇게나마 볼 수 있어 좋은 시간을 보냈다.
'자꾸 검색하는 내용' 카테고리의 다른 글
| EC2 서버 구축 기본 세팅 하기(DOCKER,EVENTBRIDGE,LAMBDA,SLACK) (0) | 2023.03.12 |
|---|---|
| [Java] ArrayList 알아보기 (0) | 2023.01.01 |
| Sql Antipatterns 스키마 및 erd (0) | 2022.12.03 |
| [디자인 패턴] 싱글턴 패턴을 알아보자. (0) | 2022.09.01 |
| 코드 시간측정 (0) | 2022.07.25 |