인천총각 Study

1. 디자인 패턴 소개( 스트래티지 패턴 )
일단 패턴 소개에 앞서서 가장 기본적으로 선행 되어야 할 내용이 있다면 상속 및 인터페이스 및 다형성의 정확한 이해다.
이를 위해서 아주 간단한 소스와 내용을 적고 그리고 본문의 스트래티지 패턴에 대해서 소개를 하는 형태로 진행을 해 나가겠다

1. 왜 다형성을 이해해야 하는가?

일단 진행에 앞서 요즘 스프링 참 많이 듣지 않는가? 여기도 스프링 저기도 스프링(아 따뜻한 봄이 오는구나..).. 우리 스터디에서도 불과 몇달전에 스프링을 약간 아주 약간맛을 아주 조금봤다. 그렇다 아주조금... 하고 싶은 이야기는 이 스프링을 공부 할때 dependency injection 이라는 개념이 있었는데 이게 지금 설명 하려는다형성을 기반으로 이해를 해야 하기 때문이다. 왜냐구 물어보면.. dependency injection 이라는게 살펴보고 나면 결국 스트래티지 패턴 하고 다를게 전혀 없기 때문이다.
즉 스프링의 dependency injection <= 스트래티지 패턴 <= 다형성 이런 과정이 성립 하기 때문에 무엇보다 앞서서 다형성을 설명 하려 한다. 말이 길었다 소스로 보자.
------------------------------------------------------------------------------------------------------------------------
public class Parent {
  private String name = "부모";
  public void printName(){
    System.out.println("name" + name);
  }
}

public class A extends Parent() {
   public void printName(){
    System.out.println("난 자식이다");
  } 
}

Parent a6 = new A();
a6.printName();
------------------------------------------------------------------------------------------------------------------------
위의 코드는 설명이 필요 없을거 같다. 메인을 구현해서 테스트해 보면 다형성이 어떤건지 바로 확인 할수 있을것이다.
잘이해가 안가거나 좀더 자세한 설명을 원하신다면 다음 링크를 따라가서 읽어 보기 바란다.
위에서 보여진 예제와 같이 다형성은 별게 아니다. 정말 그럴까? 아무것도 모를땐 ..그게 머야 당연한거아니야 별거 아니네 라고 답할수 있겠지만 이게 어떻게 쓰이는지 보게 된다면 별게 아니다 라고 하는게 아니라 "오 주여" 를 외치게 될거이다. 이제 외치러 가보자.

2. 문제에 대한 인지..

'문제에 대한 인지' 그렇다 이 말은 정말 중요하다. 모든 것에 앞서서 현재 어떤문제가 있는지 깨닫는 과정은 정말 중요한 시간이다. 문제가 무엇인지 알아야 솔루션을 제공할것이 아닌가?
지금부터는 소스를 보면서 어떻게 '문제를 인지'하게 되는지 같이 살펴보자.
상황은 다음과 같다. 아래 그림과 같이 오리클래스로 부터 상속을 받은 2개의 오리가 있다 MallaaedDuck 와 RedHeadDuck 이 그것 이다.

이녀석들은 오리로 부터 상속을 받았기에 당연히 울수있고(quack()) 물에뜨고(swim()) 각각의 모습이 틀리기에(한놈음 머리가 빨간색이지 않는가?) 오버라이딩한 display() 메소드를 가진다.
사용자는 문득 오리도 날수 있다라는 사실을 인지 하였기에 Duck클래스에 fly() 메소드를 추가 하기로 하였다. 그리고 RubberDuck(고무오리) 클래스를 추가 하였다.
위 상황에서 상속이 가진 힘에 의해 RubberDuck 역시 울수있고(quack()) 물에뜨고(swim()) 고유의 외모(display()) 그리고 날수(fly())하게 되었다.
고무오리는 날지 못한다. 더군다나 울수도 없고 말이다.
우리는 이문제를 해결하기 위해 처음에 오리마다 각각의 고유의 모습을 그려내었던(display()) 방법인 오버라이딩을 해결책으로 떠올릴수 있고.
행동 즉 메서드를 상속을 통해서 제공하므 인해 발생 하는 문제에 대해서 깨달을수 있다.(문제의 인지)

첫번째 문제는 서브 클래스에 코드가 중복이 된다는점.
두번째 문제는 모든 오리의 행동을 알기 힘들다는점.(어떤오리가 추가 될지 어떻게 알수 있단 말인가???)
세번재 문제는 코드를 변경했을때 (또는 새로운 행동을 추가 했을때) 다른 오리들에게 원치 않는 영향을 끼칠수 있다는점.
네번째 문제는 실행시점 그러니까 오리를 만들어내는 시점에 특징을 바꾸기 힘들다는 것이다.(이건 믿에서 알아 보도록 하자)

2.1 첫번재 솔루션

우리는 경험을 통해서 배운다. 글렇지 않은가? 위에서 고무오리를 하나 추가해 봄으로써 앞으로 어떤일이 펼처질수 있을지 상상 할수 있었다.(어떤 오리가 튀어 나올지 모른다 )
예전에 자바 기초를 배울때 이런 내용을 들은거 같다. 메소드의 선언만 가지고 있고 구현은 안된 인터페이스란게 있다라고..
그렇다 인터페이스를 이용해서 지금 문제를 일으키고 있는 행동들을 분리하자 라는 생각에 Flayble 과 Quackable 인터페이스를 만들고 모든 오리는 이걸 구현하게 하자!

일단 보기만 해도 문제가 있어보인다. 울지 못하고 날지 못하는 1개의 오리 때문에 나머지 오리들이 전부 2개의 인터페이스를 가져다가 구현한다....

2.2 두번재 솔루션

이제 문제는 명확해 졌다. 클레스에서 변화는 부분과 변화지 않는 부분을 분리해 내는게 첫번째 이고. 전체가 아닌 일부만 날수 있거나 울수 있게 혹은 울수 없게 만들어야 한다.
이제..드디어 다형성을 쓸 시간이 왔다. 그분이 오실 시간 이란 말이다. 다음을 보자.

이그림을 볼때 바로 소스가 어떻게 그려질지 머리에 그려지는 분도 있을것이다. 많은 노력과 좋은 환경 그리고 시간을 필요로 했을거라 생각이 된다. 이 문서를 작성하는 이유는
그러지 못한 사람들을 위해서 이므로 차근 차근 풀어 보도록 하자.

일단 추상 클래스 Duck 부터 살펴 보면 2개의 인터페이스 형식의 레퍼런스변수(참조변수)를 선언 하고 있다. 그리고 performQuack 과 performFly 2개의 메소드를 통해서 어떤 행동을
(꽥꽥 울어야 하는지 아니면 ?꽉 울어야 하는지 혹은 날개로 날아야 하는지 로켓으로 날아야 하는지 아니면 날수 없던지) 취해야 할지 행동을 제어하는 인터페이스에 위임 한다.
이 위임 이라는 용어가 조금 눈에 거슬릴거 같은데, 별거 아니다 그냥 넘겨준다는 뜻이다.
지금까지 기술한 내용을 코드로 써보면 다음과 같다.

------------------------------------------------------------------------------------------------------------------------
public abstract class Duck{
  Flyable    flyBehavior;
  Quackable  quackBehavior;

  public abstract void display();

  public void performQuack() {
   quackBehavior.quack()
  }

  public void performFly(){
    flyBehavior.fly();
  }

  public void setFlyBehavior(Flyable fb){
    flyBehavior = fb;
  }
 
  public void setQuackBehavior(Quackable  qb){
    quackBehavior = qb
  }
}
------------------------------------------------------------------------------------------------------------------------
코드 자체는 전혀 어려운게 없다. 핵심은 performQuack(), performFly() 이 두개의 메소드다. 위에서 기술한 다형성의 내용을 기억 하고 있다면 이게 어떻게 쓰일지 그림이 그려질 것이다.
setFlyBehavior()와 setQuackBehavior()의 인자인 Quackable 과 Flyable 는 아규먼트 다형성 혹은 프로모션이 라고 불리는 다형성의 형질을 이용해 값을 넘기는 아규먼트다 메인메소드 에서는 아마 다음과같이 구현될걸다
------------------------------------------------------------------------------------------------------------------------

  .
   .
   Flyable   fb = new FluWithWings();
   Quackable qb = new Squack();

   xxx.setFlyBehavior(fb);    // 한줄로쓰면 다음과 같이 된다. xxx.setFlyBehavior(new FluWithWings());
   xxx.setQuackBehavior(qb);

   xxx.performQuack();
   xxx.performFly();

   .
   .
------------------------------------------------------------------------------------------------------------------------

이렇게 만들면 부모의 메소드로 자식의 메소드를 호출하는 메서드 다형성이 발생되는 형태를 된다.
위와 같이 위임할 객체를 선택하는 seter를 만들어 두면 실행 시점에 행동에 대한 제어가 쉬워진다. Duck 클래스를 손대지 않고 단순히 performQuack과 performFly 메소드를 호출
하는것많으로 행동되야할 객체를 선택할수 있게 된다.

자 여기 까지 왔는데.. 이 스트래티지 패턴이 "어떤점이 좋은지 잘 모르겠다" 라고 하신 다면 처음에 "문제의 인지"를 할수 있었던 방법을 써보자.
이번에 태안 사고로 인해 유전자가 이상해진 오리가 나타난 거다. 이 오리는 보통오리와 달라서 로켓 추진으로 날수 있게 되었다 라고 해보자.
이 이오리가 가진 특성을 클래스에 추가하려면 어떻게 하면 될까?

간단하다. Flyable 인터페이스를 구현한 RoketWithWings라는 클래스를 하나 추가만 하면된다. 다음과 같이 말이다

멋지지 않는가?? 기능이 하나 추가 되었다고 Duck를 변경 하고 그를 상속받은 각각의 클래스를 수정 하는 이런 소모적인 일을 할필요가 전여 없다. 그렇다. 이건 영어식 표현으로 하면 Cool 한 거다. 이 패턴 꼭 기억 하고 가자

Observer Pattern
뭔가 중요한 일이 일어났을 때 객체들한테 새 소식을 알려줄 수 있는 패턴이다. 객체 쪽에서는 계속해서 정보를 받을지 여부를 실행 중에 결정할 수 있다.

 

1. Observer Pattern의 정의
Observer Pattern이란 한 객체의 상태가 바뀌면 그 객체에 의존하는 다른 객체들한테 연락이 가고 자동으로 내용이 갱신되는 방식으로 일대다(one-to-many)의존성을 정의한다.

 2. Observer Pattern의 특징
옵저버 패턴에서는 주제와 옵저버에 의해 일대다 관계를 정의된다. 옵저버는 주제객체에 의존하기 때문에 주제객체의 상태가 바뀌면 주제객체에 의존하는 모든 옵저버 객체에게 연락이 간다. 연락 방법에 따라 옵저버에 있는 값이 새로운 값으로 갱신될 수도 있다. Observer Pattern을 구현하는 방법에는 여러 가지가 있지만, 대부분 주제(subject)인터페이스와 옵저버(observer)인터페이스가 들어있는 클래스 디자인을 바탕으로 한다.

• Observer란 관찰자 이다.
• Observer Pattern은 상태 값이 변하는 Subject의 값을 체크하기 위해 생겨났다.
• Publish subscribe패턴이라고 불리우기도 한다. 컨텐츠 발행자(Subject)가 컨텐츠의 변화가 생겼을 때 구독자(Observer)에게 알려주는 방식과 비슷하기 때문이다.
• Observer는 2개 이상 존재 할 수 있다. 1:N
• Observer가 취하는 값은 읽기 전용으로 간주한다.

3. Observer Pattern의 클래스 다이어그램
? 주제(subject) : 데이터가 바뀌면 새로운 데이터 값을 옵저버들에게 보내 주는 객체
? 옵저버(observer) : 주제의 데이터가 변경되면 갱신내용을 받는 객체

  

 4. Observer Pattern의 구성
A. 주제를 나타내는 subject 인터페이스 객체에서 옵저버로 등록하거나 옵저버 목록에서 탈퇴하고 싶을 때는 이 인터페이스에 있는 메소드를 사용한다.
B. 옵저버가 될 가능성이 있는 객체에서는 반드시 observer 인터페이스를 구현해야 한다. 이 인터페이스에는 주제의 상태가 바뀌었을 때 호출되는 메소드가 있다.
C. 주제 역할을 하는 구상 클래스에서는 항상 subject인터페이스를 구현해야 한다. 주제 클래스에서는 등록 및 해지를 위한 메소드 외에 상태가 바뀔 때마다 모든 옵저버들에게 연락하기 위한 메소드도 구현해야 한다.
D. Observer 인터페이스만 구현한다면 무엇이든 옵저버 클래스가 될 수 있다. 각 옵저버는 특정 주제 객체에 등록을 해서 연락을 받을 수 있다.

 5. Observer Pattern에서 느슨한 결합(Loose Coupling)의 위력
옵저버 패턴에서는 주제와 옵저버가 느슨하게 결합되어 있는 개체 디자인을 제공한다. 두 객체가 느슨하게 결합되어 있다는 것은 그 둘이 상호작용을 하긴 하지만 서로에 대해 잘 모른다는 것을 의미한다. 주제가 옵저버에 대해서 아는 것은 옵저버가 특정 인터페이스를 구현 한다는 것뿐이며, 옵저버는 언제든지 새로 추가하거나 제거 할 수 있다. 새로운 형식의 옵저버를 추가하려고 할 때도 주제를 전혀 변경할 필요가 없으며, 주제와 옵저버는 서로 독립적으로 재사용할 수 있다. 주제나 옵저버가 바뀌더라도 서로한테 영향을 미치지는 않는다. 이런 관계를 느슨한 결합이라고 하며 느슨하게 결합하는 디자인을 사용하면 변경 사항이 생겨도 무난히 처리할 수 있는 유연한 객체지향 시스템을 구출할 수 있다. 객체 사이의 상호의존성을 최소화할 수 있기 때문이다.

6. 주제가 옵저버한테 상태 정보를 전달하는 두 가지 방식
주제가 옵저버한테 상태 정보를 전달하는 방식에는 두 가지가 있다. 주제객체에서 데이터를 보내는 방식인 푸시방식과 옵저버가 데이터를 가져오는 방식인 풀 방식이 있다. 두 가지 방식 중에는 풀 방식을 더 옳은 것으로 간주한다.

옵저버 패턴에서는 한 객체의 상태가 바뀌면 그 객체에 의존하는 다른 객체들한테 연락이 가고 자동으로 내용이 갱신되는 방식으로 일대다(one-to-many) 의존성을 정의합니다.

Singleton Pattern : 하나의 클래스 당 오직 하나의 인스턴스 만을 가지고 작업하고 인스턴스를 제어하는 단 하나의 방법만을 제공하고자 할 때 유용하다!!!
둘 이상의 인스턴스가 생성되는 것을 막기위해 클래스의 생성자를 private으로 정의하고 그 클래스의 static 메소드를 만들어서 오직 그 메소드를 통해서만 생성자에 접근할 수 있도록 하는 것이다. 그럼 이제 클래스가 이미 인스턴스화 되어 있으면 널값을 반환하고 그렇지않으면 Spooler의 인스턴스를 반환하는 메소드를 가진 Spooler클래스를 제작해보자.

------------------------------------------------------------------------------------------------------------------------
public class PrintSpooler{
//a prototype for a spooler class
//such that only one 인스턴스 can ever exist
private static PrintSpooler spooler;
private PrintSpooler(){ //privatized
}
//return only one spooler 인스턴스
public static synchronized PrintSpooler getSpooler(){
if(spooler == null) //if none created
spooler = new PrintSpooler(); //create one
return spooler;
}
public void print(String s){
System.out.println(s);
}
}
------------------------------------------------------------------------------------------------------------------------
private으로 선언되었기 때문에 Spooler클래스의 인스턴스를 직접생성할 수 없다.
------------------------------------------------------------------------------------------------------------------------
예외 던지기-
1-----------------------------------------------------------------------------------------------------------------------

public class Spooler{
// printer스풀 클래스를 위한 원형
static boolean instance_flag=false;
public Spooler() throws SingletonException{
if(instance_flag) throw new SingletonException("Only oneallowed");
else instance_flag=true;
System.out.println("printer가 열렸습니다.");
}
}

2-----------------------------------------------------------------------------------------------------------------------

public class singleSpooler{
static public void main(String argv[]){
Spooler pr1,pr2;
// 한개의 프린터를 열것이다.
System.out.println("하나의 스풀러를 열고있습니다.");
Try{
pr1=new Spooler();
}catch(SingletonException e)System.out.println(e.getMessage());
// 다른 하나의 프린터를 열려한다. 실패할 것이다.
System.out.println("두개의 스풀러를 열려합니다.");
Try{
pr2=new Spooler();
}catch(SingletonException e)System.out.println(e.getMessage());
}
}

결과--------------------------------------------------------------------------------------------------------------------

하나의 스풀러를 열고 있습니다.
printer가 열렸습니다.
두개의 스풀러를 열려 합니다.
Only one allowed
마지막 줄에서 두개의 스풀러를 사용하려는 것에 대해 예외처리를 하였다.

------------------------------------------------------------------------------------------------------------------------
Singleton ???
1. Singleton의 상속은 기초 Singleton클래스가 인스턴트화되지 않기 때문에 어려울 것이다.
2. 하나이상의 인스턴스를 허용할 수 있도록 Singleton을 변경할 수 있다.

Creational pattern(생성 패턴) :

객체의 인스턴스를 생성하는 방법, 프로그래머는 어떻게 객체를 생성하고 배열할지 신경 쓸 필요가 없다

========================================================================================================================

?? Factory Method 패턴 : Factory Method 패턴은 입력 데이터에따라 abstract한 부모 클래스의 여러 서브클래스 중 어떤 것을
반환할지를 결정하는 간단한 클래스를 제공한다. 여러 factory패턴들의 기초로써 Simple Factory 패턴을 우선 살펴볼 것이며,
그리고 나서 Factory Method 패턴을 소개할 것이다.

?? Abstract Factory 패턴 : Abstract Factory 패턴은 관련된 객체들의 여러 묶음(family) 중 하나를 생성하고 반환하는 인터페이스
를 제공한다.

?? Builder 패턴 : Builder 패턴은 복잡한 객체의 생성을 표현(representation)과 분리함으로써, 프로그램의 필요에 따라 여러
다른 표현(representation)이 생성될 수 있도록 해준다.

?? Prototype 패턴 : Prototype 패턴은 새로운 인스턴스를 복사하거나 복제하는 인스턴스화된 클래스를 제공한다. 이러한 인스턴
스는 public 메소드를 사용하여 가공될(tailor) 수 있다.

?? Singleton 패턴 : Singleton 패턴은 하나 이상의 인스턴스가 생성되지 않는 클래스를 말한다. Singleton 패턴은 이러한 인스턴스
에 접근하기 위한 하나의 포괄적인(global) 접근 포인트를 제공한다.

------------------------------------------------------------------------------------------------------------------------

Simple Factory- ex) Factory클래스에서 조건여부 판단하여 두 클래스중 하나의 클래스를 선택해 인스턴스를 반환하는 방법!!
여러 개의 클래스 중 반환할 클 래스를 결정하고 그 클래스를 반환하는 상위 추상(abstraction)클래스를 생성할 수 있다.
그러면 당신은 실제로 당신이 어떤 서브클래스를 사용할지 알 필요 없이 그 클래스 인스턴스의 메소드를 호출할 수 있다.

public class NameFactory {
Namer namer;
// Factory는 쉼표의 유무에 기초해 어떤 클래스가
// 반환될 것인지 결정한다.
public Namer getNamer(String entry) {
//comma determines name order
int i = entry.indexOf(",");
if (i > 0)
return new LastFirst(entry);
else
return new FirstFirst(entry);
}
}
------------------------------------------------------------------------------------------------------------------------

factory 클래스는 교통경찰 같은 역할을 하며, 한 계층의 서브클래스 중 어떤 것이 인스턴스화 될것인지를 결정할 것이다.

------------------------------------------------------------------------------------------------------------------------

Factory Method 패턴은 여러 면에서 쓸모가 많지만, 어떤 서브클래스를 인스턴스화할 것인지를 결정하는 클래스가 없다는 점에서 약간은 난해하다. 슈퍼클래스(superclass)는 이러한 문제에 대한 결정을 서브클래스에게 맡긴다.
패턴에서는 여러 서브클래스들 중 하나의 서브클래스를 선택해 인스턴스화하는 루틴이 존재하지 않는다. 대신에 Factory Method 패턴을 사용한 프로그램은 abstract 클래스를 이용하여 이 문제를 해결한다.
이 abstract 클래스는 객체를 생성하는 틀만을 제공하며 어떤 객체를 생성할 것인 가는 각각의 서브클래스가 결정한다.

------------------------------------------------------------------------------------------------------------------------

다음의 상황에서 Factory 메소드 사용을 고려해야 한다

?? 클래스가 생성해야 하는 객체의 클래스의 종류를 예상할 수 없을 경우

?? 클래스가 자신이 생성하는 객체를 명확히 하기 위해서 서브클래스를 사용할  경우 어떤 클래스가 생성되었는가에 대한 정보를 국한시키기 위해서 부모(base) 클래스는 abstract이고 패턴은 완전히 작동하는(working) 클래스를반환한다.

?? 부모 클래스는 디폴트 메소드를 포함하고, 디폴트 메소드가 불충분할 때는 서브클래스에서 메소드를 추가한다.

?? 여러 클래스 타입 중 어떤 클래스가 반환될 것인지 알려주는 파라미터 들이 factory에 넘겨진다.

이런 경우 클래스들은 같은 메소드 이름을 공유하지만 각각 매우 다른 무언가를 수행할 것이다.

==디자인 패턴이란?==============================================================================

컴퓨터 과학 연구자들이 디자인 패턴이라는 것을 연구하기 시작한 주요 이유는 간단하 고 또한 재활용성이 있는 프로그래밍 솔루션을 만들기 위해서 이다.
디자인 패턴은 프로젝트사이 또는 프로그래머 사이에서 객체 지향 코드를 재사용하게 하는 편리한 수단일 뿐이다.
디자인 패턴은 프로그래머들이 유용하다고 생각하는객체들간의 일반적인 상호작용(interaction) 방법들을 모은 목록(Catalog)이라고 할 수 있다.

다른 말로 디자인 패턴은 어떻게 하면 객체들이 다른 객체의 메소드, 데이터들과 뒤엉힘이 없이 통신이 이루어질 수 있는 가를 기술한 것이다.

위와 같이 객체를 분리함으로써 객체지향 프로그래밍의 목적을 항상 유지할 수 있다.

?? 디자인 패턴은 자주 발생되는 설계상의 문제를 해결하기 위한 반복적인 솔루션이다. [Smalltalk Companion]

?? 디자인 패턴은 소프트웨어 개발 영역상에서 어떠한 작업을 수행하기 위한 코딩 원칙의 집합으로 구성되어 있다. [Pree, 1994]

?? 디자인 패턴은 반복되는 구조를 설계할 때 설계를 재활용하는데 초점을 두고있다. 그에 비해 프레임워크는 세부 설계와 구현에 초점을 두고 있다. [Coplien& Schmidr, 1995]

?? 패턴은 특정 디자인 상황에서 발생되는 반복되는 설계상의 문제를 다룬다. 또한 그것의 해결 방법을 제시한다.

?? 패턴은 단일의 클래스와 인스턴스 또는 컴포넌트 들의 레벨 상위의 추상성을정의한다.[Gamma et al, 1993]

디자인 패턴은 객체를 설계하기 위한 것만은 아니다. 디자인 패턴은 객체간의 상호작용을 표현하기 위해서도 쓰인다. 이러한 관점을 가지고 쓰여진 패턴을 Communication 패턴이라고 한다.

?? Creational pattern(생성 패턴) : 프로그래머가 직접 객체를 생성하는 것보다 패턴을 이용하여 객체를 생성한다. 이 패턴을 적용하면 주어진 상황에 어떠한 적절한 객체가 생성되야 적합한지를 프로그램상으로 유용하게 표현할 수 있다.

?? Structural pattern(구조 패턴) : 객체의 그룹들을 좀더 큰 구조로 조합할 때 어떻게 하는 것이 좋은 가에 대하여 기술한 패턴들이다. 예를 들면 사용자 인터페이스나 계산 데이터에 쓰인다.

?? Behavioral pattern(기능 패턴) : 시스템상의 객체들의 통신과 통신의 흐름이 복잡한 프로그램상에서 어떻게 컨트롤되는지 정의한다.

========================================================================================================================

 

◎ 해싱에대해서?

○ 해싱이란?

해시 함수를 이용하여 키 값을 위치로 변환하고 이를 이용해
저장된 자료를 바로 찾아가는 계산 검색 방식이다.
값의 연산에 의해 직접 접근이 가능한 구조를 해시테이블(hash table)
해시테이블을 이요한 탐색을 해싱(hashing)

 

○ 해싱구조..

레코드 키들의 집합을 버켓주소의 집합에 대응시킨다는 의미에서 사상함수라 한다.
가장 이상적인 해싱 함수는 키 집합의 한 레코드와 버켓 주소 집합의 한 레코드가
1 : 1 대응하여 해시 테이블의 정해진 범위에 고르게 분포되어 있는것을 뜻함.

-저장 및 검색 과정-

키 값 –> 해싱 함수 –> 해시 주소(버킷 주소) –> 해시 테이블

 

해싱 함수 구현부분-
----------------------------------------------------------------------------------------
public static int hash(Object key) // hashing method >> private
{   
  int sum = 0;
  byte compare[] = null;
     compare=((String)key).getBytes(); // 문자열을 바이트로 환산해주는 메서드 >> 리턴값 : 배열
   
  for(int i=0;i<((String)key).length();i++)
  {
  sum+=(int)compare[i];
  }
    
  int h=(sum & 0x7FFFFFFF) % capacity;
  return h;
 }
------------------------------------------------------------------------------------------

○ 해시 테이블

해상함수로부터 계산된 함수값에 해당하는 위치에 각 레코드를 한 개 이상 보관할 수 있는
버켓들로 구성된 기억 공간이며, 주어진 key값을 가지고 해당 레코드를 빠르게 검색하기 위한
수단을 제공하며 레코드의 삽입과 삭제를 용이하게 한다.

해시 테이블은 크기가 파일보다 커야한다. n개의 레코드에 대해 n개의 해쉬 주소를 생성
하는 해쉬 함수를 찾는것은 불가능 하기 때문.
일반적으로 부하율(load factor) 75%이상이면 일정의 테이블 공간을 늘려주는 것이 좋다.
그이상의 급격하게 성능 저하가 발생!!

 

○ 버켓

일종의 자료구조로 해싱함수에 의해 계산된 주소인 홈 주소에 레코드를 저장하기 위해 마련된 기억공간.

 

○ 해싱함수란?

탐색 키를 간단화하는 함수를 해싱 함수(hashing function) 라 하며,
탐색 키를 받아서 해시 주소를 생성하는 기능을 한다.
이 해시 주소가 바로 간단화된 탐색 키라고 할 수 있고. 자리수가 몇 안 되는 정수이고 곧 배열의 번호이다.

※ 좋은 해시 함수 조건
- 주소 계산이 빠르게 구해져야 한다.
- 서로 다른 레코드의 계산된 값이 가급적 중복되지 안하야 한다(충돌이 적어야한다)

○ 해싱함수의 종류

-제산법(Division) : 나머지 연산자(%)를 사용하여 테이블 주소를 계산하는 방법!!
                    ＊ 버켓주소 = 키 값 % 해쉬테이블 크기

-제곱법(Mid-Saure) : 레코드 키 값을 제곱한 후에 결과 값의 중간 부분에 있는 몇 비트를
                     선택하여 해시 테이블의 홈 주소로 사용, 심볼 테이블 응용에서 자주 사용
                    ＊ k = 35270 제곱시 테이블의 크기가 10,000일때(중간 4비트선택)
         11243972900 -> 1243ㅣ9729ㅣ00 -> 9729가 주소값

-숫자 분석법(Digit-Analysis) : 레코드 모든키들 내에서 각 자리별로 어떤 분포인지 조사하여
          비교적 고른 분포를 나타내는 자릿수를 필요한 만큼 선택하여 사용
                               * 정적 파일에 유효, In/out 빈번히 발생할경우 비효율적

 

-폴딩법(Folding) : 레코드 키의 마지막 부분을 제외한 모든 길이가 동일하게 여러부분으로 나누고
                   이를 모두 더하거나 배타적 노리합을 취하여 홈주소로 이용하는 방법

  탐색키 : 123ㅣ203ㅣ241ㅣ112ㅣ20
                  
  ＊이동폴딩 : 각부분의 값을 계산하기 위해 마지막을 제외한 모든 부분을 이동시
        최하위 비트가 마지막 부분의 자리와 일치하도록 우측끝을 맞추어 더한 값

        123+203+241+112+20 =699      

  ＊경계폴딩 : 나누어진 각 부분의 경계선을 종이 접듯이 접어 역으로 정렿한 다음 더한 값

        123+302+241+211+20=897

                    
- 기수변환법 , 무작위 방법 등이 있음

 

○ OverFlow 해결

- 선형조사법,이차조사법,이중해싱법,체이닝 의 방법 사용 (선형법과 체이닝 많이사용)

＊ 선형 조삽법(선형 개방 주소법) : 충돌이 일어난 키값을 다른 비어있는 버킷을 찾아 저장한다.
       이 때 비어있는 버킷은 순차적으로 찾는다

 

＊ 체이닝(Chaining) : 오버플로우 문제를 연결 리스트로 해결
        각 버켓에 고정된 슬롯을 할당하는 것이 아니라 각 버켓에, 삽입과 삭제가
        용이한 연결리스트를 할당
        버켓내에서는 원하는 항목을 찾을때는 연결리스트를 순차 탐색!

 

○ 동적 해싱법

 해시 테이블 대신에 트라이라는 자료구조 사용
 트라이 : 입력키의 각 비트값에 따라 2개의 가지로 분리되도록 만들어진 것
 
 키 값의 맨 오른쪽 비트부터 검사 하여 0일경우 첫번째 레벨의 위쪽 1일경우 아래쪽 으로 분기
 끝에서 두번째 비트를 검사하여 그값이 0이면 두번째 레벨의 위쪽 1이면 아래쪽으로 분기
 ......순차적으로 오른쪽에서 왼쪽으로 키값을 비교해 나가면서 분기한다.,

------------------------------------------------------------------------------------------------------------------------

구현

----Entry Class---------------------------------------------------------------------------------------------------------

public class Entry
{
 public Object key, value; //key,value 필드 분리
 public Entry next;  // Node 개념 적용 - 자기 참조

 public Entry(Object key, Object value) {
      this.key = key;
      this.value = value;
    }

 public Object getKey() {  //key 리턴
      return key;
    }
   
 public Object getValue() {  //value 리턴
       return value;
    }

 public void setValue(Object value) { //value 설정
      this.value = value;
    }
}

----HashTable Class----------------------------------------------------------------------------------------------------

public class HashTable
{
   private static final int CAPACITY = 10;  //기본테이블 크기
   private static int capacity;
   public Entry[] hTable;  // 해쉬테이블은 배열로 구성되어 있고 각각의 배열에는 엔트리가 들어감 

   public HashTable(int capacity) // 파라미터가 테이블 용량을 넘겨줄경우 생성자
   { 
     this.capacity = capacity;
     hTable = new Entry[capacity];  // 테이블 크기만큼 엔트리 생성 해서 해쉬 테이블 생성
   }

   public HashTable() // 파라미터가 없을경우
   {   
     this(CAPACITY);  // 기본값 크기로
   }

   public static int hash(Object key) // hashing method >> private
   {   
     int sum = 0;
     byte compare[] = null;
     compare=((String)key).getBytes(); // 문자열을 바이트로 환산해주는 메서드 >> 리턴값 : 배열
    
     for(int i=0;i<((String)key).length();i++)
     {
      sum+=(int)compare[i];
     }
    
     int h=(sum & 0x7FFFFFFF) % capacity;
     return h;
  }

  
   public void put(Object key, Object value) // 넣기
   { 
     int h = hash((String)key);   // key 값으로 해싱
     Entry cur = hTable[h];  // 해싱값에 해당하는 배열칸값
     Entry entry = new Entry(key, value); // 엔트리 형성
    
     if (hTable[h] == null) //
      { 
       hTable[h] = entry;    // 입력된 값 저장
      }
     else {  // 해시값 충돌시
         while (cur.next != null)// 노드 끝까지
          {      
            if(cur.getKey().equals(key)) // 혹시나 키값이 같은 자료 입력을 시도랬다면
            {  
            cur.setValue(value);   // 해당엔트리의 자료값만 변경
            break;  // 그다음 끝냄
            }
           cur = cur.next;    // 리스트가 끝날때까지 next 로 찾아감
          }
         cur.next = entry;   // 리스트의 끝에 입력된 엔트리 달기
        }
   }
   

  public void searchMap(Object word) // 검색 메서드
  {  
   int flag = 0; // 결과 상태
   Object result = null; // 결과값
   Entry cur = hTable[hash(word)];
  
   if (cur == null)
    flag = 0;
   else
   {
    while(cur != null)
    {
     if (cur.getKey().toString().equals((String)word))
      {
      flag = 1;
      result = cur.getValue(); break;
      }
     else
      cur = cur.next;
    }
   }
  
   //검색결과 출력
   if (flag == 0 ) System.out.println("검색결과가 없습니다.");
   else System.out.println("검색결과가 있으며 값은 " + (String)result + " 입니다.");
  }
 
 

   public void printMap() // 출력
   { 
     Entry cur;                   // 출력할 엔트리를 '포인팅' 하기 위해 정의한 변수
     for(int i=0; i<capacity; i++) // 테이블 크기 수 만큼
     { 
       System.out.print("|"+i+"|\t"); 
       cur = hTable[i];     // i번 배열에 있는 엔트리를 받아오기
      
       if((cur == null))        // 비어있을경우
        System.out.print("null");  // null 출력
       else
       { 
         while(cur != null)
         {      // 엔트리 끝이 더이상 없을 때까지
           System.out.print("Key : "+ cur.getKey() +"  Value : "+ cur.getValue()+"  ");  // 현재 엔트리의 키값과 자료값을 불러와 출력
           cur = cur.next;        // 다음번 엔트리로 넘어가기
         }
       }
       System.out.println("");   // 줄바꾸기 
     }      
   }
  
  
 }

----Testinput Class-----------------------------------------------------------------------------------------------------

public class Testinput
{

 public static void clearScreen() // 화면 초기화
 {
      for (int i = 0; i < 80; i++)
        System.out.println("");
 }
 
 
 public static void main(String[] args) throws IOException
 {
     HashTable map2 = new HashTable();
  int msel;
        String con;  // 계속 여부
        do
        {
          //clearScreen();
    System.out.println("메뉴를 선택하세요");
    System.out.println("1. 입력");
    System.out.println("2. 출력");
    System.out.println("3. 검색");
    System.out.println("4. 종료");
    
    BufferedReader ar = new BufferedReader(new InputStreamReader(System.in));
    msel =Integer.parseInt(ar.readLine());
    
    switch (msel)
    {
     case 1: // 입력
     {
      System.out.println("key : ");
      BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
      String b=br.readLine().toString();
      System.out.println("value : ");
      BufferedReader cr = new BufferedReader(new InputStreamReader(System.in));
      String c=cr.readLine().toString();
      map2.put(b,c);
      break;
     }
     case 2: // 출력
     {
      map2.printMap();
      break;
     }
     case 3: // 검색
     {
      System.out.println("search : ");
      BufferedReader dr = new BufferedReader(new InputStreamReader(System.in));

      String d=dr.readLine().toString();
      map2.searchMap(d);
      break;
     }
     case 4: // 종료
     {
      return;
     }
    }     
  
  } while (true);
  
  
  
 }

}

----TestChaining Class--------------------------------------------------------------------------------------------------

public static void main(String[] args)
{
     HashTable map1 = new HashTable();  // 첫번째 맵 형성
     map1.put("태희","011-234-5348");  // 자료입력
     map1.put("미","011-214-7678");
     map1.put("동훈","015-434-8378");
     map1.put("종훈","011-2674-5878");
     map1.put("Hut","016-214-2678");
     map1.put("Ohr","013-134-1678");
     System.out.println("map1 is  ");
     map1.printMap();  // 자료출력
    
     map1.searchMap("Ohr");
     map1.searchMap("종훈");
    

     //System.out.println(map1.hash("Tor"));
     //System.out.println(map1.hash("Rad"));
    
    
    

     HashTable map55 = new HashTable();
     map55.put("a","1234");
     map55.put("b","3456");
     map55.put("c","9874");
     map55.put("d","5478");
     map55.searchMap("c");
    
    
   }
 }

------------------------------------------------------------------------------------------------------------------------LRU 기법? 주기억장치에 저장된 시점과 관계없이, 사용률이 가장 저조한 페이지를 교체하는것!

◆◆ Stack 과 Queue

◆ 1. Stack

  ㉠ 정의

      여러 개의 데이타 항목들이 일정한 순서로 나열된 자료 구조로, 한쪽 끝에서만 새로운 항목을 삽입하거나 기존 항목을 삭제할 수
      있는 선형 구조.

  ㉡ 특징

      Last- In-First-Out List (후입 선출) : 먼저 삽입된 것은 나중에 삭제되고, 나중에 삽입된 것이 먼저 삭제.

      push : Data 를 넣는 것.

      pop : 넣어둔 Data 를 꺼내는 것.

      top : Data 를 저장하는 위치

  ㉢ 연산

       S를 스택, x를 데이터 요소(element)라고 하자. 그러면 스택에서는 아래와 같은 중요한 연산이 존재하는 것을 알 수 있다.

       S.top(): 스택의 가장 윗 데이터를 넘겨준다.만약에 비었다면 이 연산은 정의불가 상태다.

       S.pop(): 스택의 가장 윗 데이터를 지우고 그 값을 넘겨준다.스택이 비었다면 연산 정의불가 상태.

       S.push(): 스택의 가장 윗 데이터로 x를 넣는다.

       S.empty(): 스택이 비었다면 참을 주고,그렇지 않다면 거짓이 된다.

       또한, 스택연산을 목록(list) 연산으로 표현할 수도 있다.

       S.top(): S.retrieve(S.first())

       S.pop(): S.top(),S.delete(S.first())

       S.push():S.insert(x,pNull)

       S.empty():S.first()==pNull

 

◆ 2. Queue

  ㉠ 정의

      여러 개의 데이타 항목들이 일정한 순서로 나열된 자료 구조로 한쪽 끝에서는 삽입만 할 수 있고, 삭제는 반대쪽 끝에서만 할 수 있
      도록 되어 있는 선형 구조.

  ㉡ 특징

       First In First Out (선입선출) : 큐에 저장된 데이터 항목들 중에 먼저 삽입된 것은 먼저 삭제되고, 나중에 삽입된 것은 나중에 삭제.

       put : Data 를 넣는 것.

       get : Data 를 꺼내는 것.

       front(head) : Data 를 put 할 수 있는 위치.

       rear(tail) : Data 가 있어 get 할 수 있는 위치.

       Overflow : Queue 가 꽉 차서 더 이상 Data 를 넣을 수 없는 경우 (put 할 수 없는 경우)

       Underflow : Queue 가 비어 있어 Data 를 꺼낼 수 없는 경우 (get 할 수 없는 경우)

  ㉢ 종류

       가. 선형 Queue : 막대 모양으로 된 Queue 이다. 크기가 제한되어 있고 빈 공간을 사용하려면 모든 Data 를 꺼내거나 Data 를 한
                               칸씩 옮겨야 한다는 단점이 있다.

       나. 환형 Queue  : 선형 Queue 의 문제점을 보완한 것이 환형 Queue 이다. front가 Queue 의 끝에 닿으면 Queue 의 맨 앞으로 Data 를 보내어 원형으로 연결 하는 방식.

       다. Linked Queue  : Linkedlist 를 사용한 것으로써, Queue  의 길이를 쉽게 늘릴 수 있어 Overflow 가 발생하지 않는다.

                                  필요에 따라 환형으로 만들 수도 있으며, 환형으로 만들지 않아도 삽입과 삭제가 제한되지 않아 편리하다.

 

◆◆ 3. Simulation (Java)

1. node 클레스 설계
------------------------------------------------------------------------------------------------------------------
public class Node {
 
 public Node(int v){
  value = v;
 }
 
 public int value;
 public Node next;   // 자기 참조!!
}
------------------------------------------------------------------------------------------------------------------

 

2. LinkedList 클레스 설계
------------------------------------------------------------------------------------------------------------------
public class LinkedList {
 Node header;

 public LinkedList(Node h) {
  header = h;
 }

 public void append(Node node) {
  Node last = header;
  while (last.next != null) {
   last = last.next;
  }
  last.next = node;
 }
 
 public Node getHeader(){
  return header;
 }

 public void remove_back() //링크드 리스트에 뒤에 있는걸 삭제
 {
  Node last = header;

  if (last.next == null)  // elements 가 하나만 있는 상황이므로 끊을필요 없다
  {
  }
  else
  {
   while (last.next.next != null) { // 두번째 연결된 elements 의 next 값이 없을때 까지 루프
    last = last.next;
   }
   last.next = null; //  마지막 에 연결된 elements 의 next 를 null 값을 넣어 끊기
  }
 }
 
 public void remove_front() //링크드 리스트에 앞에 있는걸 삭제
 {
  header = header.next; // 헤더 를 다음 값으로 바꾸기
  
 }
  
}
------------------------------------------------------------------------------------------------------------------

 

3. Array 로 Stack 구현
------------------------------------------------------------------------------------------------------------------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class IntStack_A {
 
    private int[] data;

    private int top;   // stack 맨위

    private int many_items; // 현재 Stack 에 몇 개의 원소가 있는지를 저장해 놓은 변수

    private int stack_size; // Stack 의 전체 크기
   
    private BufferedReader br ;

public IntStack_A(int size) // size : 스텍의 크기
    {
        data = new int[size];

        stack_size = size;      

        top = -1; // stack 이 비어 있을 때

        many_items = 0;

     System.out.println("값을 입력하세요 :");
     try {
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));

   printf1();   
   System.out.println("");
   System.out.println("1.삭제(POP)  2.삽입(PUSH)");
   br = new BufferedReader(new InputStreamReader(System.in));
   String sd=br.readLine();
   if (sd.equals("1"))
   {
   pop();
   printf1();
   }
   
   else if (sd.equals("2"))
   {
   push(99);
   printf1();
   } 
   
  } catch (NumberFormatException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  } catch (IOException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }
       
    }
   
   
    public void push(int number) // push()는 Stack 의 맨 위에 쌓아놓을 수 있다  >> data 배열에 숫자를 넣음
    {
        data[++top] = number; //++top 연산을 통해서 top 은 push 함수를 호출할 때마다 하나씩 위로 올라가서 Stack 의 맨 위를 언제나 가리키게 됨
                                         // 배열 이므로 제일 나중에 집어넣은 원소의 Index 를 보유

        many_items++; // Stack 에 저장된 원소의 갯수 1 증가
    }

   
    public int pop() // 맨 위에서만 빼낼 수 있다
 {
  many_items--; // Stack 에 저장된 원소의 갯수 1 감소
  return data[top--]; // 배열에서 맨위의 값을 반환하고 인덱스 를 1 감소시킴
 }
   
   

    public void printf1() // 배열 출력
    {
     for(int i=0;i<many_items;i++){
     System.out.print(data[i]+",");
  }
    }

     public static void main(String[] args)
     {
 new IntStack_A(5);
      }
}

------------------------------------------------------------------------------------------------------------------

 

4. Array 로 Queue 구현
------------------------------------------------------------------------------------------------------------------
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class IntQueue_A {
 
    private int[] data;

    private int rear;   // Queue 맨위

    private int many_items; // 현재 Queue 에 몇 개의 원소가 있는지를 저장해 놓은 변수

    private int Queue_size; // Queue 의 전체 크기
   
    private BufferedReader br ;

public IntQueue_A(int size) // size : Queue 크기
    {
        data = new int[size];

        Queue_size = size;      

        rear = -1; // Queue 가 비어 있을 때

        many_items = 0;

     System.out.println("값을 입력하세요 :");
     try {
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));
      br = new BufferedReader(new InputStreamReader(System.in));
      push(Integer.parseInt(br.readLine()));

   printf1();   
   System.out.println("");
   System.out.println("1.삭제(POP)  2.삽입(PUSH)");
   br = new BufferedReader(new InputStreamReader(System.in));
   String sd=br.readLine();
   if (sd.equals("1"))
   {
   pop();
   printf1();
   }
   
   else if (sd.equals("2"))
   {
   push(99);
   printf1();
   }  
   
  } catch (NumberFormatException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  } catch (IOException e) {
   // TODO Auto-generated catch block
   e.printStackTrace();
  }       
    }
       
    public void push(int number) //  data 배열에 숫자를 넣음
    {
        data[++rear] = number; //

        many_items++; // Queue 에 저장된 원소의 갯수 1 증가
    }
   
    public void pop() // 맨 위에서만 빼낼 수 있다
 {

  for (int i=0;i<many_items;i++)
  {
   data[i] = data[i+1];
  }

  many_items--; // Queue 에 저장된 원소의 갯수 1 감소
 }

    public void printf1() // 배열 출력
    {
     for(int i=0;i<many_items;i++){
     System.out.print(data[i]+",");
  }
    }

 public static void main(String[] args) {
  new IntQueue_A(5);
 }
}
------------------------------------------------------------------------------------------------------------------

 

5. LinkedList 로 Stack 구현
------------------------------------------------------------------------------------------------------------------
public class LinkedListStack {
 public static void main(String[] args) {
  LinkedList list = new LinkedList(new Node(50));
  list.append(new Node(20));
  list.append(new Node(30));
  print(list.getHeader());
  list.remove_back();
  print(list.getHeader());
  list.append(new Node(10));
  print(list.getHeader());
  list.append(new Node(60));
  print(list.getHeader());
  list.remove_back();
  print(list.getHeader());
  list.remove_back();
 }

 private static void print(Node header) {
  Node list = header;
  while (list != null) {
   System.out.print(list.value + " -> ");
   list = list.next;
  }
  System.out.println();
 }
}
------------------------------------------------------------------------------------------------------------------

 

6. LinkedList 로 Queue 구현
------------------------------------------------------------------------------------------------------------------
public class LinkedListQueue {
 public static void main(String[] args) {
  LinkedList list = new LinkedList(new Node(50));
  list.append(new Node(20));
  list.append(new Node(30));
  print(list.getHeader());
  list.append(new Node(10));
  print(list.getHeader());
  list.append(new Node(60));
  print(list.getHeader());
  list.remove_front();
  print(list.getHeader());
 }

 private static void print(Node header) {
  Node list = header;
  while (list != null) {
   System.out.print(list.value + " -> ");
   list = list.next;
  }
  System.out.println();
 }
}

◆◆ Array 와 Linkedlist : 같은 타입의 여러가지 요소 (집합) 를 저장

◆ 1. Array

  ㉠ 정의

      index 와 index에 대응하는 데이터들로 이루어진 자료 구조를 나타낸다.

      즉, 동일한 자료형이고 메모리상에 연속적으로 놓인 데이터를 일괄적으로 처리하기 위해서

      만든 하나의 집합 형식으로 묶어놓은 자료 구조이다.

  ㉡ 특징

       메모리 할당이 연속적이어서 인덱스 사용시 검색이 빠르다.

       메모리 관리면에서 공간의 낭비가 심하다.

       자료의 삽입및 삭제가 어렵다.

 

◆ 2. Linkedlist

  ㉠ 정의

      연결 리스트, 링크드 리스트(linked list)는 각 노드가 데이터와 포인터를 가지고 한 줄로 연결되어 있는 방식으로 데이터를 저장하
      는 자료 구조이다.

      이름에서 말하듯이 데이터를 담고 있는 노드들이 연결되어 있는데, 노드의 포인터가 다음이나 이전의 노드와의 연결을 담당하게
      된다.

  ㉡ 특징

      메모리 할당이 비연속적이며, 크기가 동적이므로 낭비가 없다.

      보통 element 와 element 를 가로 질러서 조건에 맞을 때까지 순차 검색하므로 검색이 느리다.

      자료의 삽입및 삭제가 쉽다.     

  ㉢ 종류

      가. 단순 연결 리스트 : 각 노드에 자료 공간과 한 개의 포인터 공간이 있고, 각 노드의 포인터는 다음 노드를 가르킴

      나. 이중 연결 리스트 : 단순 연결 리스트와 비슷하지만, 포인터 공간이 두 개가 있고 각각의 포인터는 앞의 노드와 뒤의 노드를 가
                                     리킴

      다. 원형 연결 리스트 : 일반적인 연결 리스트에 마지막 노드와 처음 노드를 연결시켜 원형으로 만든 구조

 

◆◆ 3. Arrays and linked lists 중 어떤 것을 사용할지 결정하기 (중요!!)

   ㉠ 사이즈 면에서....

      Arrays 은 사용자의 필요에 따라 1차 혹은 다차 원으로 구현할수 있다.

      linked lists 는 태생적으로 1차원이며, 각각의 요소(element)들은 이전 요소와 다음 요소의 포인터를 가지고 있다.

 

   ㉡ 할당 면에서....

      Arrays는 만들어질때부터 사이즈가 정적으로 정의 된다. 게다가 Arrays에서 메모리 할당은 인접하며 끊어지지 않는다.

      >>>> Contiguous Memory Allocation - 연속 메모리할당 (프로세스들에게 연속된 메모리 공간을 할당해 주는 것)

      그러므로 Arrays는 디자인할 당시에 요소(element)의 최대 숫자를 알고있을 때 전형적으로 사용된다.

      이러한 접근방식으로 구현한 배열 단점은 커다란 배열은 아마도 사용되지 않는 큰 메모리가 필요로 한다는 것이다.

      특히나 이렇게 요소의 최대값으로 디자인된 배열은 종종 그들의 용량에 비해 턱없이 작게 저장되기도 한다.

      그리고 오래된 os 를 가진 초소형 장치들과 같은 경우에 메모리 제약이 당신이 사용할수 있는 배열의 크기를 제한할 수도 있다.

      반면에, linked lists 는 보통 동적이다. 실시간으로 필요할 때 마다 줄이거나 키울 수 있다.

      이러한 특징들로 인해서 linked lists 는 요소의 수를 몰랐을 때 좀더 효과적으로 사용될 수 있다.

      뿐만아니라 메모리가 요소요소에 의해 할당되므로, 비연속적이다.

      이런 불확실성을 다루는데서 오는 단점은 linked lists에서 추가하거나 지울때에 미리 할당된 배열된 요소들의 값을 정의할때 보다 
      좀더 부하가 있다 라는 것이다.

      그러나 linked lists에 얼마나 많은 메모리가 할당될 것이냐에 대한 유일한 제한은 당신의 목적에 의해서 사용하는 힙메모리의 크기
      에 의해서 결정되어진다.

   ㉢ 요소를 접근하는 방식에 있어서....

      Arrays 안에 있는 요소들은 그들의 인덱스를 통해서 접근할 수 있다. 그러므로 데이터 접근은 찾을 요소를 알면 빠르고 쉽다.

      만약 요소의 인덱스를 모르고 어떤 키값에 의해서 정렬되어있을 경우에 보다 효율적으로 특정 요소를 찾아낼 수 있다.

      이러한 알고리듬은 특정 요소가 위치하는 비교 의 최소값만을 허락하며,

      Arrays를 병합하거나 정렬하는 효율적이고 안정적인 몇가지 알고리듬들이 존재한다.

      그러나 Arrays는 요소의 순서가 쉽게 변할 때 비효율적이다. 요소가 자주 지워지거나 삽입되는 배열을 관리할 경우에 배열의 모든
      요소를 옮겨나를 필요가 있다.

      반면에, linked lists는 보통 요소와 요소를 가로 질러서 조건에 맞을 때까지 검색한다.

      왜냐하면 linked lists 에 대한 메모리는 연속적이라고 보장할 수 없기 때문이다.

      이러한 검색방법은 (인덱스와 같은 다른 데이터 구조체를 포함하지않는) 리스트를 검색하는 유일한 방식이다.

      비연속 메모리의 윗쪽부분은 리스트를 다시 정의하는 것으로, 단순히 링크를 조정하는 것을 포함한다.

      요소의 삽입과 삭제는 포인터 수정을 필요로 하고 실제적인 데이터의 전송은 전혀 필요로 하지 않는다.

   ㉣ 규칙들을 깨는 것

      거의 모든 언어에서 두가지 방식을 모두 지원을 한다.

      C에서 변수나 객체를 가르키는 포인터는 만약 그 포인터가 할당된 배열 안에서 첫번째 요소를 가르킬 때 배열처럼 사용할 수 있다.

      이렇게 포인터를 배열처럼 사용할 때 이 포인터의 크기조절이 필요하면,

      realloc() 라는 펑션이 메모리의 새로운 블럭을 할당하고 새로운 위치로 존재하는 모든 요소를 옮긴다.

      이러한 기법은 연속적인 메모리 할당 과 요소 인덱싱을 유지하는 가운데 배열의 동적인 리사이징을 가능하게 한다.

      Java 에서는 제공되는 linked-list class 가 인덱싱 되는 기법 뿐만아니라 top, next, previous, etc. 과 같은 표준 리스트 메서드를
      모두 지원한다.

      indexOf(), get(), and set() 과 같은 메서드들은 리스트의 요소가 흡사 배열과 같이 엑세스 되도록 도와준다.

      게다가 Java는 리스트 클래스의 향상된 리사이즈가능한 배열을 나타내는 "ArrayList class " 를 제공한다.

      이 두가지 클래스 모두 그들의 리스트 표현방식에서 실제 배열로 변환되는 메서드를 지원한다.

      프로그래밍 언어가 갈수록 진화되고있고 두가지 구조체의 구분이 점점 모호해지고 있다.

      하지만 어디서 이러한 구조체들이 고안되었는지 그리고 새로운 클래스안에서 어떻게 쓰여지고 있는지 기억하는것은 항상 중요하
      다.

      이러한 새로운 개선들은 프로그래머에게 자세한 부분을 숨기곤 함에도 불구하고, 요구되는 컴퓨터적인 부하 와 자원들은 변하지
      않는다.

   ㉤ 결정내리기....

      만약 당신의 데이터가 다차원적인 구조체로 표현이 되어지거나, 요소들의 숫자를 미리 알게 되거나, 일관된 성질을 가지고 있다면
      array 가 제일 좋다.

      만약 당신의 데이터가 1차원으로 쉽게 표현이 된다거나, 요소의 숫자들을 알지 못한다거나, 목적상 데이터가 자주 변한다고 생각
      이 되어질거라 예상될 때라면  linked lists 가 좀더 효율적이다.

      만약 당신의 데이터가 자주 검색되거나 접근되고 수정이 잦질 않다면 array 가 당신이 기대하는 운영에서 최소의 부하를 제공한다.

      만약 당신이 정기적으로 요소를 추가하거나 제거할때, 특별히 정렬된 순서를 그대로 유지할 필요가 있을 때 linked lists를 사용하
      는 것이 낫다.

      결국엔 당신의 데이터 와 당신의 운영면에서의 필요가 당신의 목적에 어떤 구조체가 최선인지 결정할 것이다.

원문:
http://articles.techrepublic.com.com/5100-10878_11-1050183.html