목차

1. 연결리스트의 개념
2. 연결리스트의 종류 2-1 단순연결리스트 2-2 원형 연결리스트 2-3 이중 연결리스트 2-4 이중 원형 연결리스트

1. 연결리스트의 개념

정의

① 연결리스트는 첫 번째 노드를 가리키는 헤드 포인터가 필요하다

② 포인터가 다음 노드의 위치를 가리키는 구조로, 전체 노드는 논리적으로 서로 연결된 상태

③ 마지막 노드는 노드의 포이터를 Nil or Null이라 한다

④ 각각 노드는 기억장소에서 서로 이웃할 필요 없다 = 물리적으로 연속적x

⑤ 링크필드로 인한 기억공간이 많이 필요하며, 알고리즘 구현이 복잡하고 탐색시, 비효율적이다.

노드란?🧐

자기자신을 참조하는 구조체를 이용해 정의한다 (data필드+포인터 저장된 link필드)

2. 연결리스트의 종류

2-1. 단순연결 리스트

① 거꾸로 갈 수 있는 방법은 없다. 탐색시간은 포인터를 이용해 순차적, 시간복잡도 O(n) ② 노드를 삽입, 삭제의 경우 선행 노드를 알고 있어야한다. ③ 특정 노드 액세스를 위해서는 처음 노드부터 검색한다.

단순연결 리스트 삽입

코드

procedure INSERT(Head,item,Y)
/* Y: 삽입할 노드 , X : 삽입 후, Y의 선행 노드 */
call GETNODE(Y)
/* Y노드 생성 */
DATA(Y) ← item
/*Y노드에 데이터 값 저장 */
if(Head=nill) then Head ← Y
LINK(Y) ← nill
/* Head가 NULL인 경우, Head가 Y를 가리키도록하라 */
else LINK(Y) ← LINK(X)
    LINK(X) ← Y
/* 마지막 노드는 항상 NULL */
end INSERT

void insert(listPointer *first, listpointer x)
{
listPointer temp;
MALLOC(temp, sizeof(*temp));
temp →data =50;
if(*first){
temp → link = x → link;
x→ link = temp;
}
else{
temp →link =NULL;
*first =temp;
}
}

단순연결 리스트 삭제

코드

procedure DELETE(X,Y,Head)
/* Y: 삭제할 노드 X: Y의 선행노드*/
if(Head=nil) call List-empty

if(X=nil) then Head ← LINK(Head)
/* 첫번째 노드 삭제 */
else LINK(X) ←LINK(Y)
/*중간 노드 삭제*/
call RET(Y)
end DELTE

void delete(listPinter *first,listPinter trail,listPinter node){
/* 리스트로부터 노드를 삭제, trail은 삭제될 x의 선행 노드, first는 리스트의 시작 */
if(rail)
    trail →link = x →link;
else
    *first= (*first) → link;
    free(x);
}

2-2. 원형 연결리스트

정의

① 마지막 노드가 null link 대신 리스트의 처음 노드의 포인트를 가진다. ② 마지막 노드를 변경하기 위해서는 마지막을 찾을 때 까지 모든 노드 탐색 ** ③ head가 마지막을 가리킬 경우, **길이에 상관없이 첫 번째 앞 마지막 노드 위에 일정한 시간으로 노드를 삽입하 수 있다.

장단점

장점

• 어느 한 노드로부터 다른 모든 노드에 접근 가능
• 임의의 노드 검색 시 현재노드 부터 검색 가능

단점

• 노드 검색 시 무한루프에 빠질 수 있다.
• 무한루프 문제는 head 포인터를 두어 방지 가능하다.

노드삽입

- 앞에 삽입

procedure INSERT(T,Y) //T는 마지막 노드를 가리킨다.
    if T = nill then T ← Y  // 리스트가 빈 상태로 T가 Y를 지시
    LINK(Y)← T //Y는 자기자신을 가리킨다.
    else LINK(Y) ← LINK(T)// 새 리스트가 첫 번째 노드를 지시
    LINK(T)←Y // 마지막 노드의 링크필드가 새 노드를 지시
end INSERT

① 원형 리스트가 빈 상태로 T가 새로운 노드 Y를 가리킨다 ② 새 노드의 Y의 링크 필드가 첫 번째 노드를 가리키게한다 ③ 마지막 노드의 링크 필드가 새로운 노드 Y를 가리키게 한다.

void insertFront(listPinter last, listPPinter node){
if(!(*last)){ //공백일 경우, last가 새로운 항목을 가리키도록 한다.
    *last =node;
    node → link=node;
    }
    else{// 공백이 아닌 경우, 리스트 앞에 새로운 항목 삽입
    node → link = (*last) →link;
    (*last)→link=node;
    }
 }

2-3. 이중 연결리스트

정의

① 원형리스트의 뒤로 순화할 수 없다는 점과 삭제의 번거로움의 단점을 보완했다 ② 어떤 노드에 대해 다음 노드 뿐만 아니라 전 노드까지 알수 있도록 하여 양방향 탐색 가능

③각 노드에 좌 우측2개의 포인터가 있으며, 각 포인터는 각각 좌우 노드를 가리키는 형태이다 ④운영체제의 동적 메모리 관리에 적합하다.

• X = RLINK(LLINK(X)) = LLINK(RLINK(X))

장점

• 양방향 검색이 가능해 속도가 빠르고** 선행노드 검색이 쉽다**
• 한 노드의 포인터 파괴시, 복구 가능
• 리스트 운행에 따른 알고리즘이 간단하다

  단점

• 두 개의 링크를 저장할 기억공간이 낭비된다.

2-4. 이중 원형 연결리스트

정의

마지막 노드의 RLINK는 처음 노드를 가리키게 하고 처음 노드의 LLINK는 마지막 노드를 가리킨다

장점

• 마지막 노드까지 데이터 저장 시, 빈 노드를 찾아 입력할 수 있는 융통성 부여
• 무한루프에 빠지는 것을 방지

  단점

• 알고리즘 구현의 복잡성

Head노드란?🧐

데이터를 가지지 않고, 삽입 삭제 코드를 간단하게 할 목적으로 만들어진 노드

가지고 있는 내용

• 첫 번째 노드 포인터
• 리스트 길이
• 마지막 노드 포인터
• 참조계수(자신을 참조하고 있는 포인터 수)
  #### 오늘은 여기까지 🙂

목차

1. 기본준비 1-1 java 11설치 1-2 IntelliJ IDEA 설치 1-3 H2 설치
2. 프로젝트 생성 2-1 스프링부트 스타터 사이트를 이용해 프로젝트 생성 2-2 프로젝트 생성 web 통해 확인
3. 버그 3-1 open을 누른 후, tag mismatch 에러가 나올 경우 3-2 로컬호스트 에러가 나올 경우
4. 알아가는 정보 알아가는 정보

1. 기본준비

1-1 Java 11 설치

java 11SE kit 설치

• 환경설정 Path 경로 지정(설정이 안되었을 경우) 시스템 속성 > 고급 > 환경변수 > 시스템변수 > path > javapath경로 추가

👉 확인 법 cmd창에서 javac 입력하거나 java -version 입력

1-2 IntelliJ IDEA 설치

IntelliJ 다운로드

** Community window.exe 선택 다운로드**

① Create Dsktop Shorcut : 윈도우 OS 환경 확인 ② Update PATH Variable : 환경변수 자동 추가 ③ Update Context Menu : 프로젝트 폴더 열기 ④ Create Associations : 자바 사용(확장자)

1-3 H2 설치

h2 다운로드 👉 1.4.200 설치! 최근 버전 설치시, 일부 기능 정상작동 불가

2. 프로젝트 생성

2-1 스프링부트 스타터 사이트를 이용해 프로젝트 생성

스프링 부트 스타터

Dependencies에 Spring web, Thymeleaf 추가!😀 Generate 클릭하여 파일 다운로드

다운로드한 파일을 원하는 폴더 위치에 옮긴 후, 압축 풀기 IntelliJ에서 Open or Import 선택

2-2 프로젝트 생성 web을 통해 확인

✋ build가 완료되었다면 src / main과 test 존재해야한다.

main파일 실행 웹브라우저에서 localhost:8080 입력 결과는 아래와 같아야한다.

3. 버그

open을 누른 후, tag mismatch 에러가 나올 경우

경우 1. Java 버전11 이외 다른 상위 버전이 설치된 경우

파일 > 프로젝트 구조 선택 아래와 같이 설정한 후 확인 -> 적용

경우 2. embed tomcat 관련 문구가 나올 경우, tomcat 관련 설치가 안되어있을 경우

파일 > 설정 > 플러그인 아래와 같이 검색 후, 설치한다.

버그 메세지가 뜰 경우, gradle 설정을 아래와 같이 해준다.

4. 알아가는 정보

build.gradle

sourceCompatibility = '11' //java 11과 호환됨(맞춤)
repositories {
    mavenCentral() //open 된 싸이트 dependencies를 해당 싸이트에서 다운
}
dependencies {
    implementation 'org.springframework.boot:spring-boot-starter-thymeleaf'
    implementation 'org.springframework.boot:spring-boot-starter-web'
    testImplementation ('org.springframework.boot:spring-boot-starter-test'){
        exclude group : 'org.junit.vintage', module:'junit-vintage-engine'
    }

}