[자료구조] 연결리스트

 

 

연결리스트

 

1. 리스트

 

리스트: 데이터의 목록을 다루는 구조가 단순한 자료구조

  - 선형리스트=> 순서 중요

  - 선형구조: 데이터가 순차적으로 저장되는 끊어지지 않는 구조

 

 

리스트 관련 주요 연산

  - 자료 검색, 전체 검색/순회/출력

  - 순서 변경, 전체 목록 갯수 계산

  - 자료 추가/삭제/변경

  - 빈 목록인지 여부 판단

 

 

 

 

 

2. 선형 리스트

 

선형리스트 : 순서대로 나열된 동일 유형의 항목들(순서 중요)

   Ex)요일, 카드, 한글 자음 모임

=> 데이터가 메모리에 저장될 때, 저장 시작 위치부터 빈자리 없이 순서대로 저장 (연속되는 기억장소에 저장)

 

 Ex) 정수형 자료형 = 4byte 크기 가짐

=> 메모리 주소는 4byte씩 증가 + 메모리에 (23, 25, 35) 순서로 값 저장

선형 리스트의 논리적인 순서와 메모리에 저장된 물리적 순서 일치!

 

 

 

 

 

3. 배열로 구현한 선형 리스트

 

배열의 한계점

  - 원소 추가/삭제에 어려움

  - 배열의 크기(원소 개수) 고정

 

 

삽입연산: 삽입위치 다음의 항목들을 이동하여야 함.

 

 

 

삭제연산: 삭제위치 다음의 항목들을 이동하여야 함

 

 

 

 

4. 연결리스트

 

 

연결리스트(linked list)

  :자료들을 하나씩 차례대로 연결하는 방식의 자료구조

     => 배열의 단점들을 보완/개선하는 역할

     =>자료 이외에 다음 자료를 가리킬 주소(즉 포인터) 추가 필요

 

      * 노드 = <데이터, 링크>

      * 데이터(data) 필드 : 자료의 원래 값, 즉 데이터 값을 저장

      * 링크(link) 필드 : 다음 노드의 주소 값(포인터) 저장

 

  

 

 헤드 포인터

  - 연결리스트의 첫번째 노드를 가리키는 별도의 포인터 변수

  - 결과적으로 전체리스트를 가리키는 역할

    (연결 리스트의 첫 노드를 알아야만 전체의 노드에 접근할 수 있다.)

 

 

* 동적 메모리 할당

  : 프로그램 실행 중에 메모리를 할당하는 것

    - 메모리가 필요할 때 마다 할당을 해주는 기법 => 동적으로 리스트 크기 필요한 만큼만 유지 가능

    - 연결리스트는 원하는 만큼 노드를 동적으로 추가/삭제 가능!

 

 

 

 

5. 배열과 연결리스트

 

 

 

 

 

6. 연결리스트 장단점

 

장점

- 삽입, 삭제가 보다 용이함.

- 연속된 메모리 공간 불필요.

-원소 개수(크기)를 동적으로 바꿀 수 있음 (코딩을 통해 프로그램 실행 중간에 바꿀 수 있음).

 

 

단점

- 링크 정보를 추가로 유지. (메모리 공간 낭비)

- 구현이 어려울 수 있음.

- 포인터 사용으로 오류 자주 발생.

- 동적 메모리 할당이 필요.

 

 

 

 

 

 

 

7. 연결리스트의 종류

 

 - 단순 연결 리스트

 

  - 원형 연결 리스트

 

  - 이중 연결 리스트 

 

 

 

 

 

 

 

 

---

 

 

옛날엔 그렇게 연결리스트가 어려웠는데, 다시 한번 공부하니 조금은 가깝게 느껴지는 것 같다

예습복습의 중요성을 이제야 깨닫는 것 같은 느낌..?

앞으로 예습....은 오바고..... 복습이라도 잘 하는 사람이 되는 것을 목표로 잡아야지!

 

 

 

다음 내용은 단순연결리스트!