세상의 모든 Software 지식을 정리

1. 중첩 클래스( Inner Class) ->하나의 클래스 내부에 또 다른 클래스가 내포되어 있는 상태(클래스 관리의 효율을 높임) *특징 -중첩되는 클래스는 하나 이상 가능. -Outer 클래스 멤버를 Inner 클래스에서 사용가능 -Outer 클래스에서 Inner 클래스 멤버 사용불가능 (사용하고 싶으면 객체를 직접 발생시켜야함) - 일반 중첩 클래스 내부에서는 static과 관련된 멤버를 선언할 수 없음 예)    Class Outer{       내용부:       class Inner{         내용부:       }    } } * 중첩 클래스 객체 생성 Outer 객체 1=new Outer(); Outer.Inner 객체2=객체1.new Inner(); 2. 정적 중첩 클래스 (Static Inner Class) *정의 - 중첩 클래스 내부에서 static과 관련된 멤버를 선언할 수 있는 클래스. *특징 - 클래스의 이름 앞에 static 예약어가 붙음 - static의 특성상 객체를 독립적으로 만들 수 있음 - static멤버를 선언할 수 있고, static 메소드도 만들어 사용할 수 있음. - Outer 클래스의 static멤버만 Inner에서 사용할 수 있음 *형식 class Outer{     내용부:       static class Inner{         내용부:       } } *객체 생성 방법   Outer.Inner 객체 = new Outer.Inner();     -  Outer 클래스의 객체가 없어도 Inner ...

1. 객체지향 설명 2. static 설명 3. 가비지컬렉션 원리 설명 4. 그러면 가비지 컬렉션말고 프로그래머가 메모리 관리를 어떻게 할 수 있는지 설명하라(weaked해쉬맵???같은것??) 5. 리플렉션에 대해 알기 6. Wrapper Class란 무엇인가?

*리플렉션이란? 객체를 통해 클래스의 정보를 분석해내는 기법이다. 스프링을 공부하다보면 BeanFactory라는 Spring Container개념을 학습하게 된다. 이 BeanFactory는 애플리케이션이 실행한 후 객체가 호출될 당시 객체의 인스턴스를 생성하게 되는데 그때 필요한 기술이 Reflection 이다. 자바는 스크립트 언어가 아닌 컴파일 언어이다. 물론 .java-> .class-> 실행 이라는 2단계의 메커니즘을 가지고 있지만, 컴파일 언어로 분리하는게 옳다. 원래 자바에서는 동적으로 객체를 생성하는 기술이 없었다. 그리고 동적으로 인스턴스를 생성하는 Reflection으로 그 역할을 대신하게 된다. 가정을 해보면, 만약 객체의 메모리만을 알고 있고, 그리고 객체의 형태에 대해 모른다고 생생각해보자. 리플렉션으로 형은 알고 있지만, 형변환을 할 수 없는 상태에서 객체의 메소드를 호출할 수 있다. Class c=Data.class; //Class c=Class.forName("클래스 이름"); Method[] m=c.getMethods(); Field[] f=c.getFields(); Constructor[] cs=c.getConstructor(); Class[] inter=c.getInterfaces(); Class superClass=c.getSuperClass();

NAVER D2 글: http://d2.naver.com/helloworld/1329 *가비지 컬렉션 과정 'stop-the-world' : GC를 실행하기 위해 JVM 애플리케이션이 실행을 멈추는 것이다. 가비지컬렉션이 시작되면 Garbage Collection을 담당하는 쓰레드를 제외하고 모든 쓰레드가 정지한다. GC작업을 완료한 이후에 중단했던 작업을 다시 시작한다. 어떤 GC알고리즘을 사용하더라도 이 stop-the-world는 발생한다. 대개의 경우 GC튜닝은 이 stop-the-world시간을 줄이는 것이다. Java는 프로그램 코드에서 메모리를 명시적으로 지정하여 해제하지 않는다. 가끔 명시적으로 해제하려고 해당 객체를 null로 지정하거나 System.gc() 메서드를 호출하는 개발자가 있다. null로 지정하는 것은 큰 문제가 안 되지만, System.gc() 메서드를 호출하는 것은 시스템의 성능에 매우 큰 영향을 끼치므로 System.gc() 메서드는 절대로 사용하면 안 된다(다행히도 NHN에서 System.gc() 메서드를 호출하는 개발자를 보진 못했다). *가비지 컬렉터는 두 가지 가설에 의해 만들어졌다. 대부분의 객체는 금방 접근 불가능한 상태가 된다. 오래된 객체에서 젊은 객체로의 참조는 아주 적게 존재한다. *Old영역에 있는 객체가 Young영역의 객체를 참조하는 경우가 있을때에는 어떻게 처리 될까? 이런경우를 처리하기 위해서는 Old영역에는 512바이트의 덩어리 (chunk)로 되어있는 카드 테이블(card table)이 존재한다. 카드 테이블에는 Old영역에 있는 객체가 Young영역의 객체를 참조할 때마다 정보가 표시된다. Young영역의 GC를 실행할 떄에는 Old영역에 있는 모든 객체의 참조를 확인하지 않고, 이 카드테이블만 뒤져서 GC대상인지 식별한다. 카드 테이블은 write barrier를 사용하여 관리한다. write barrier는 M...

public int [ ] mergeArrays ( int [ ] myArray , int [ ] alicesArray ) { // 조건 myArray 와 alicesArray둘다 각각 이미 정렬되어 있어야한다. // set up our mergedArray int [ ] mergedArray = new int [ myArray . length + alicesArray . length ] ; int currentIndexAlices = 0 ; int currentIndexMine = 0 ; int currentIndexMerged = 0 ; while ( currentIndexMerged < mergedArray . length ) { boolean isMyArrayExhausted = currentIndexMine >= myArray . length ; boolean isAlicesArrayExhausted = currentIndexAlices >= alicesArray . length ; // case: next comes from my array // my array must not be exhausted, and EITHER: // 1) alice's array IS exhausted, or // 2) the current element in my array is less // than the current element in alice's array if ( ! isMyArrayExhausted && ( isAlicesArrayExhausted || ( myArray [ currentIndexMine ] < alic...

네이버 D2글 : http://d2.naver.com/helloworld/831311 * HashMap은 보조 해시 함수(Additional Hash Function)를 사용하기 때문에 보조 해시 함수를 사용하지 않는 HashTable에 비하여 해시 충돌(hash collision)이 덜 발생할 수 있어 상대으로 성능상 이점이 있다. Java 8 HashMap에서의 Separate Chaining Java2 부터 Java 7까지의 HashMap에서 Seperate Chanining 구현 코드는 조금씩 다르지만,  구현 알고리즘 자체는 같았다. 만약 객체의 해시 함수 값이 균등 분포(uniform distribution)이라고 할 때, get()메소드에 대한 기대값은  이다.  자바에서는 이보다 더 나은  을 보장한다. 데이터의 개수가 많아지면, Seperate Chaning에서 링크드 리스트 대신 트리를  사용하기 때문이다. 데이터의 개수가 많아지면 과 의 차이는 무시할 수 없다. 게다가 실제 해시 값은 균등 분포가 아닐뿐더러, 설사 균등 분포를 따른다고 하더라도 birthday problem이 설명하듯 일부 해시 버킷 몇 개에 데이터가 집중될 수 있다. 그래서 데이터의 개수가 일정 이상일 때에는 링크드 리스트 대신 트리를 사용하는 것이 성능상 이점이 있다. 링크드 리스트를 사용할 것인가 트리를 사용할 것인가에 대한 기준은 하나의 해시 버킷에 할당된 키-값 쌍의 개수이다. 예제 5에서 보듯 Java 8 HashMap에서는 상수 형태로 기준을 정하고 있다. 즉 하나의 해시 버킷에 8개의 키-값 쌍이 모이면 링크드 리스트를 트리로 변경한다. 만약 해당 버킷에 있는 데이터를 삭제하여 개수가 6개에 이르면 다시 링크드 리스트로 변경한다. 트리는 링크드 리스트보다 메모리 사용량이 많고, 데이터의 개수가 적을 때 트리와 링크드 리스트의 Worst Case 수행...

*HashMap과 같이 해싱을 구현한 컬레션 클래스에서는  Object클래스에서 정의된 hashCode()를 해시함수로 사용한다. Object클래스에 정의된 hashCode()는 객체의 주소를 이용하는 알고리즘으로 해시코드를 만들어 내기 때문에 모든 객체에 대해 hashCode()를 호출한 결과가 서로 유일한 훌륭한 방법이다. *String 클래스의 경우 Object로부터 상속받은 hashCode()를 오버라이딩해서 문자열의 내용으로 해시코드를 만들어 낸다. 그래서 서로 다른 인스턴스 일지라도 같은 내용의 문자열을 가졌다면 hashCode()를 호출하면 같은 해시코드를 얻는다. HashSet에서 설명했던 것과 같이 서로 다른 두 객체에 대해 equals()로 비교한 결과가 true인 동시에 hashCode()의 반환값이 같아야 같은 객체로 인식한다. HashMap에서도 같은 방법으로 객체를 구별하며, 이미 존재하는 키에 대한 값을 저장하면 기존의 값을 새로운 값으로 덮어쓴다. 그래서 새로운 클래스를 정의할 때, equals()를 재정의(Overriding)해야 한다면 hashCode()ㅗ 같이 재정의해서 equals()의 결과가 true인 두 객체의 해시코드(hashCode()의 결과값)가 항상 같도록 해주어야 한다. 그렇지 않으면 HashMap과 같이 해싱을 구현한 컬렉션 클래스에서는 equal()의 호출결과가 true이지만 해시코드가 다른 두 객체를 서로 다른 것으로 인식하고 따로 저장할 것이다.

*Arrays클래스의 sort메소드를 보던 중, parallelSort()라는 메소드를 보게 되었다. 이 정렬 메소드는 DualPivotQucikSort를 사용하여 일반 sort()메소드와 같지만, 다중 스레드를 사용할시 훨씬 좋은 정렬 성능을 보인다고 나와있다. 특히, 메소드 안에 다음과 같은 조건이있다. p = ForkJoinPool.getCommonPoolParallelism()) == 1  ForkJoinPool은  기본 개념은 큰 업무를 작은 업무 단위로 쪼개고, 그것을 각기 다른 CPU에서 병렬로 실행한후 결과를 취합하는 방식이다. 마치   분할정복 알고리즘 과 흡사하다. 여러 CPU들을 최대한 활용하면서 동기화와 GC를 피할수 있는 여러 기법이 사용되었기 때문에, Java 뿐 아니라 Scala에서도 널리 쓰이고 있는 병렬처리 기법이다.  또한 C,C++을 위한 Thread Building Block(TBB) 나 C#의 Task Parallel Library또한 Fork Join Framework의 개념을 가지고 있다. *ForkJoinPool의 절차를 조금 더 보자면 1) 큰 업무를 작은 단위의 업무로 쪼갠다. 2) 부모 쓰레드로부터 처리로직을 복사하여 새로운 쓰레드에서 쪼개진 업무를 수행(Fork)시킨다. 3) 2을 반복하다가, 특정 쓰레드에서 더 이상 Fork가 일어나지 않고 업무가 완료되면 그 결과를 부모 쓰레드에서 Join하여 값을 취합한다. 4) 3을 반복하다가 최초에 ForkJoinPool을 생성한 쓰레드로 값을 리턴하여 작업을 완료한다. <ForkJoinPool의 성능의 핵심 : Work-Stealing> 기본적으로는 newCachedThreadPool이나 newFixedThreadPool 처럼 ExecutorService의 구현체이다. 그러나 일반 ExecutorService 구현 클래스와는 기본적으로 다른 점이 하나 존재한다. 바로...

*String 클래스는 public final class 로 되어 있다. 또한 값 비교를 위한 Comparable<String>을 구현하고 있다. *특히, 문자열을 저장하기 위해  private final char value[]; 로 되어있는데 final로 되어 있기 때문에 초기값 이후 값을 변경할 수 없다. 즉 새로운 문자열을 붙일 경우 새로운 객체를 생성해야 한다는 것을 알 수 있다. 반면에 StringBuffer은 final로 되어 있지 않다. 대신 transient가 붙어 있어 직렬화가 불가능하다. *compareTo메소드는 문자열의 길이만을 비교한다.

 참고 하면 좋은 사이트 https://www.tutorialspoint.com/java/util/arraylist_toarray.htm *interface로 구현 됨 <추상메소드> 1. int size() 2. boolean isEmpty() 3. boolean iscontains(Object o) 4. Iterator<E> iterator(); 5. Object[] toArray() - Array로 바꾸는 메소드 6. boolean add(E e) - 현재 element 의 끝에 붙이는 메소드 7. boolean remove(E e)- 첫 번째 element를 제거하는 메소드, element가 존재한다면 8. boolean containsAll(Collection<?> c) - 특정한 collection타입 요소들을 모두 포함하고 있을 때 true를 리턴함 9. boolean addAll(Collection<? extends E> c) - 10. boolean addAll(int index, Collection<? extends E> c) - 특정 지점 부터 c 데이터들을 모두 집어넣는 메소드 11. boolean removeAll(Collection<?> c) - 모든 요소들을 삭제하는 메소드 12. boolean retainAll(Collection<?> c)-

<빠진 숫자 찾기> http://www.ardendertat.com/2011/09/27/programming-interview-questions-4-find-missing-element/ http://codercareer.blogspot.kr/2013/02/no-37-missing-number-in-array.html

< 선택 정렬 > 시간복잡도: O(N^2) ->선택 정렬은 비교는 많지만, 교환은 적은 알고리즘이다.  장점: 정렬된 상태를 역순으로 정렬시 효율적이다.  단점: 정렬된 데이터에 소수의 데이터 추가시 이를 다시 정렬하기 위해서는 최악이다.  < 버블 정렬> 시간복잡도: O(N^2) ->데이터를 하나씩 비교할 수 있어서 정밀하게 비교 가능하나 비교횟수가 많아지므로 성능면에서 좋은 방법이 아니다. 첫번째 원소부터 마지막 원소까지 비교가 끝나면 가장 큰 원소를 마지막 자리로 정렬한다. < 퀵정렬 > 시간복잡도 최악- O(N^2) 평균- O(NlogN) ->캐시라는 지역적 특성에 의해 실제적으로 NlogN보다 좋은 성능을 보여 가장 많이 사용하는 정렬이다. 단점으로는 안정성이없다. 안정성이 없다는 것은 정렬되기 이전의 데이터 동일한 데이터끼리의 순서를 정렬 후에도 유지하고 있는가이다. < 삽입정렬 > 시간복잡도 : O(N^2) 버블정렬이 조금 비효율적인 면이 있기에 비교횟수를 효율적으로 줄이기 위해 고안된 삽입정렬이다. 버블정렬은 비교대상의 메모리 값이 정렬되어 있음에도 불구하고 비교연산을 하는 부분이 있는데 삽입정렬은 비교적 비교횟수를 줄이고 , 정렬된 값은 한번도 교환이 일어나지 않고 N-1의 비교만 일어난다. < 쉘 정렬 > 시간복잡도: O(N^1.25) 삽입정렬의 개념을 확대하여 일반화한 정렬방법이다. 알고리즘이 간단하여 간단히 구현할 수 있다. 수행능력도 삽입정렬보다 우수하다. 멀리있는 레코드들 끼리 비교 및 교환 될 수 있으므로, 어떤 데이터가 제 위치에서 멀리 떨어져 있다면 여러 번의 교환이 발생하는 버블정렬의 단점을 해결 할 수 있다. <병합 정렬> 시간복잡도: O(NlogN) 작은 단위부터 정렬해서 정렬된 단위들을  계속 병합해가면서 정렬하는 방식이다. 알고리즘...

*스트래티지 패턴 동적으로 알고리즘을 교체할 수 있는 구조 알고리즘 인터페이스를 정의하고, 각각의 알고리즘을 클래스별로 캡슐화하여 각각의 알고리즘을 교체 사용가능하게 한다. 즉, 하나의 결과를 만드는 목적(메소드)은 동일하나, 그 목적을 달성할 수 있는 방법(전략, 알고리즘)이 여러가지 존재할 경우, 기본이 되는 템플릿 메소드 패턴과 함께 가장 많이 사용한다.

*Factory Pattern은 인스턴스의 생성과정을 숨긴 채, 다 만들어진 인스턴스를 반환해주는 역할을 한다. 때문에 Factory Pattern은 생성과정에서 여러가지 작업을 해줘야 하는 상황에 사용한다. Factory 패턴에서 중요한 것은 생성할 객체의 추상화에 있다. (abstract를 말하는 것이 아니다.) 생성과정에서 추상화된 객체를 반환하여 상속받는 모든 자식의 클래스를 다루게 된다.즉, 생성과정의 변환에 관계없이 프로그래밍을 가능하게 하며 생성과정을 캡슐화하여 외부에 노출을 줄이게 된다. 그리고 코드의 확장성을  크게하여 새롭게 추가되는 기는ㅇ에 유연하게 대처할 수 있게해준다. 그리고 코드의 커플링을 낮추어 코드 유지차원에서도 효과를 톡톡히 볼 수 있다. Abstract factory Pattern을 사용하면 Strategy Pattern을 사용할 때 처럼 큰 유연성을 가져다 준다. 생성루틴을 확장할 수 있고, 프로그램 실행중에도 생성루틴을 다이나믹하게 갈아낄 ㅅ 있다. 그럼에도 사용하는 측의 코드에 전혀 영향이 가지 않는다는게 최대 장점이다. 하지만 코드의 양이 많아지고, 객체를 생성하기 까지 다소 복잡한 과정을 거쳐야 한다. 생성과정에 규모가 작다면 오히려 코드의 이해도를 떨어뜨리는 패턴이 될 가능성을 가직 있으나 신중하게 생각해서 적용해야 한다.

10진수 -4는 이진법으로 11111100이다. 이를 오른쪽으로 2번 비트 쉬프트 하게 되면 다음과 같다. 부호 확장 부호 확장이란 무엇일까요? 부호 확장이란  데이터의 비트 크기를 확장 하는 것입니다. 예를들어, 8비트를 16비트로 만드는 경우처럼요.. 양수값 의 부호 확장에는  상위자리를 0 으로 채우면 되고, 음수값 의 부호 확장에는  상위 자리를 1 로 채우면 끝!! 이처럼 양수, 음수 모두의 경우에도 부호 비트의 값으로 상위 자리를 채우면 부호 확장이 가능합니다 .

우선 ALTER문은 이미 존재하는 테이블의 구조나 형식등을 바꾸기 위해 사용한다.  따라서, 칼럼의 구조나 형식을 변경하기 위해 ALTER명령을 사용하게 된다.  ALTER 명령어는 다음과 같다.  <테이블 이름 변경> ALTER TABLE 테이블명 RENAME 바꿀이름 또는 RENAME TABLE 테이블명 TO 바꿀이름 <칼럼 추가> - 마지막에 추가: ALTER TABLE 테이블명 ADD COLUMN 칼럼이름 칼럼타입 - 지정 칼럼 뒤에: ALTER TABLE 테이블명 ADD COLUMN 칼럼이름 칼럼타입 AFTER 칼럼이름 - 제일 앞에: ALTER TABLE 테이블명 ADD COLUMN 칼럼이름 칼럼타입 FIRST <칼럼 삭제> ALTER TABLE 테이블명 DROP COLUMN 칼럼이름 <칼럼 변경> ALTER TABLE 테이블명 MODIFY 컬럼이름 컬럼타입 ALTER TABLE 테이블명 CHANGE 칼럼이름 새 칼럼이름 칼럼타입 <인덱스에 새 항목 추가> ALTER TABLE 테이블명 ADD INDEX (칼럼이름) <인덱스 삭제> ALTER TABLE 테이블명 DROP INDEX(칼럼이름) DROP INDEX 인덱스 이름 ON 테이블명 <제약 조건 추가> 테이블 생성시 제약조건을 추가하지 않았다면 추가할 수 있다. ALTER TABLE 테이블명 ADD CONSTRAINT 제약조건명 제약조건 (칼럼명); 예) ALTER TABLE 테이블명 ADD CONSTRAINT PLAYER_FK FOREIGN KEY (TEAM_ID) REFERENCES TEAM(TEAM_ID); * FOREIGN KEY 제약조건을 위와 같이 추가하면 PLAYER 테이블의 TEAM_ID 컬럼이 T...

남자 8만개만 뽑고 싶다면 인덱스를 사용하는 것이 좋을까? 사용하지 않는 것이 좋을까? 참고: http://choko11.tistory.com/entry/%EC%9D%B8%EB%8D%B1%EC%8A%A4-1-%EA%B0%9C%EB%85%90%EC%A2%85%EB%A5%98%EC%A3%BC%EC%9D%98%EC%82%AC%ED%95%AD

n-2 개의 숫자가 Array나 List에 저장되어 있습니다. 원래는 n개의 일련숫자(이를테면 6,7,8,9,..,6+(n-1)) 였는데, 가장 작은 수와 가장 큰 수를 제외하고 숫자 두개를 삭제한 후에 순서를 랜덤하게로 재 배열한 것입니다. (즉, Sorting이 되어있지 않습니다.) 문제는 제거된 두 숫자를 찾아내는 것인데, 조건은 계산에 필요한 storage에 제약이 있습니다. 즉, O(N)보다 작다는 것입니다. (참고로 O(n)개의 storage 가 주어진다면 너무나 쉬운 문제가 되겠지요?) 그리고 Computing Time은 O(n)입니다. 예를 들어서 12,7,9,5,4,10,11 이 주어진다면, 없어진 두 숫자는 6과 8이 되겠네요. (하루나 이틀후에 답이 없으면, 답을 올리겠습니다. 정답이 반드시 하나일 필요는 없겠지요.) 답: 전체 엘리먼트와 합과, 전체 엘리먼트의 곱을 계산하면 되네요. 2개의 숫자를 빼기 전의 숫자들은 중간에 빠지는 숫자가 없는 일련 번호니까, 전체 합과 곱이 어떤 값이어야 하는 지 알 수 있습니다. 이제, 두개의 숫자를 X, Y라고 하면, X + Y = A, X*Y = B 에서 A, B의 위의 계산에서 알 수 있습니다. public static void main(String[] args) { // TODO Auto-generated method stub int[] number={4,5,7,9,10,11,12}; int lastIndex=number.length-1; int size=number[lastIndex]-number[0]+1; int sumTotal=(number[0]+number[lastIndex])*size/2; int mulTotal=1; for(int i=number[0];i<=number[number.length-1];i++){ mulTotal*=i; } int p...

일단 ConcurrentHashMap 과 HashMap 의 차이점은 다 알고 있다는 전제하에 포스팅을 작성 한다. 이 포스팅을 하게된 이유는 사실 어떤분이 나에게 ConcurrentHashMap 과 HashMap 의 차이점을 아냐고 물어봤고 물론 알고 있어서 쏼라쏼라 대답을 했지만 (Multi-Threaded 환경에서 thread safe 여부) 거기에서 끝나지 않고 또 물어보시더라 ConcurrentHashMap 이 왜 Thread 에 safe 한지? 어떤 원리인지 아세요? 그래서 나는 사실 정확하게 알진 못했지만 대략 MySQL 의 innodb 처럼 row-level lock 걸듯이 접근하고 있는 해당 Key 값에 lock을 걸지 않을까요? 라고 대답을 했다. 이 대답은 후에 찾아 보니 반은 맞고 반은 틀리더라… 그리고 다시한번 정확하게 정리한다.. —————————————————————————————————— 보통은 우리가 Multi-threaded 환경에서 key-value 저장소가 필요할때 자바에서 사용하는 것이 크게 1. HashTable 2. HashMap 3. ConcurrentHashMap 이렇게 있는데 파악을 하기 위해서 각 자바 source 를 까보았다. 가장 중요한 Get, Set 부분만 보면 1. HashTable public synchronized V More ...get(Object key) public synchronized V More ...put(K key, V value) 보이는가? 메소드 레벨에서 synchronized 를 걸어 버린다. 2. HashMap 얘는 볼것도 없이 synchronized 가 없다. 따라서 속도는 빠르지만 Multi-threaded 환경에서 그냥 쓰면 여러 Thread 에서 동시 접근시 Exception 이 난다. 3. ConcurrentHashMap 얘는 특이하게 synchronized 가 아니라 lock 을 사용한다. V More .....

자바에서는 Card c=new Card(); System.out.println(c)와 System.out.println(c.toString())과 같다. 그 이유는 PrintStreamClass에는 print메소드가 있다. public void print(Object obj){    write(String.valueOf(obj)); } public static String valueOf(Object ob){      return (obj==null)?:"null":obj.toString(); }

*링크드 리스트의 탐색시간은 O(N)이 걸린다. 그래서 자료의 탐색에는 별로 좋지 않다. 그러나 이를 응용한 Skip List를 사용하면 O(logN)에 구현이 가능하다. 이 원리는 다음과 같다. 스킵 리스트 SKIP LIST 스킵 리스트 이해하기 스킵 리스트는 정렬된 상태를 유지하면서 데이터를 삽입, 삭제하고 탐색할 수 있는 데이터 구조체(data structure)이다. 여기 설명은  윌리엄 퓨(William Pugh, Skip Lists: A Probabilistic Alternative to Balanced Tress)  의 논문(1990년 발표)에 근거해 설명한다.   살바토르도 이 논문을 바탕으로 Sorted Set에 사용되는 스킵 리스트를 구현했다. 스킵 리스트는 링크드 리스트의 단점을 개선하는 데서 시작한다.   여기서 설명하는 링크드 리스트는 정렬된 상태를 유지하는 리스트이다.   이런 링크드 리스트에서 n 번째 node를 찾으려면 n 번 비교를 해야 한다. 아래 그림에서 보는 것처럼 값이 '80' 인 노드를 찾으려면 비교를 9번 해야 한다.   최악의 경우 모든 노드를 비교해야 한다.   그림 1-a   정렬된 링크드 리스트 레벨을 갖는 스킵 리스트 탐색 시간을 단축하기 위해서는 비교 횟수를 줄여야 한다.   여기서 아이디어를 낸 것이 노드에 포인터를 두 개를 갖게 해서 두 번째 포인터는 하나 건너뛰어서 다음 노드를 가리키도록 한다.   그림 1-b   레벨 2 스킵 리스트 위 그림에서 보는 것처럼 홀수 번째 노드는 포인터 하나만 갖고, 짝수 번째 노드는 포인터를 두 개 갖은 것이다.   이렇게 구현하면 하나씩 건너 뛰어 비교할 수 있기 때문에 n 번째 노드를 찾는데 n/2 + 1 번 비교하면 된다.   비교 횟수를 반으로 줄이는 획기적인 아이디어이다.   값이 '80' 인 노드를 찾는데 비...