자료구조(배열, LinkedList)

자료구조 개념은 여기를 참고
https://ko.wikipedia.org/wiki/%EC%9E%90%EB%A3%8C_%EA%B5%AC%EC%A1%B0


1. 배열(array)
   일정한 데이터 공간에 자료를 집어넣는다.
    이때 할당 순서별 자료 순서가 정해진다.
    아래 표에서 시작 자료는 1, 순서도 1이다.
    직접 주소를 넣기도 하고, 순서 값을
    각 숫자에 추가하기도 한다.
   장점이라면 공간이 적다는거고
   단점이라면 삽입할때 그 뒷부분은 한칸씩 밀어내야 하니
    자료가 많은 경우 성능이 떨어질 수 있다.
 

1

2

3

4

5

2. 링크드 리스트(linked) or 연결 리스트

   자료와 함께 다음 순서 자료 위치를 같이 저장한다.

    뒤에것만 저장하면 단순

1 |2주소

2 |3주소

3 |4주소

4 |5주소

5 |null

    , 양쪽에 전후 정보를 저장하면 이중

head| 1 |2주소

1주소| 2 |3주소

2주소| 3 |4주소

3주소| 4 |5주소

4주소| 5 |null

    맨끝 정보 다음 주소는 보통 null인데 

    이걸 처음 자료 순서로 지정하면 원형

head| 1 |2주소

1주소| 2 |3주소

2주소| 3 |4주소

3주소| 4 |5주소

4주소| 5 |1주소

    각자 링크를 가지고 있기 때문에 수정이 용이하다.
     근데 리스트 갯수가 적다면 굳이 쓸 필요는 없다.

3. 해시충돌 및 처리 방법
 (1) 해시함수 : 임의 길이 데이터를 숫자 또는 고정된
     자료로 만드는 방법이고 보통은 다른 글자면 숫자도
      틀리게 나오지만 가끔 충돌 나는 경우가 발생 할 수 있다.
     해시함수를 쓰는 이유는 속도 때문이다.
 (2) 해시충돌
     그 현상을 해시충돌이라고 하고 이를 피하기 위해서는
   <1> 방어적인 코드를 작성
   <2> 다른 좀더 무결한 해시함수를 사용
     이중 두가지를 다 사용한다.
 (3) 방어적인 코드(해시충돌방지)는?
     array의 경우에 순서가 같은 해시 값이 나오면
   <1> 그 옆에 끼워넣기
   <2> 2차원 배열형태로 그 밑에 넣기
     정도로 앞축된다.

작성시 참고한 블로그
WebBrain 내 생각을 만들어내는 기술

위키피디아-해시충돌

위키피디아-해시함수

IT 취준생을 위한 이야기 - 해시충돌은 무엇..

위키피디아-자료구조