[자료구조 - C언어] 자료구조 제11강: 연결 리스트 - 개념과 기본 동작들(1)

//공부 기록용 포스팅입니다. 틀린 부분이 있을 경우 댓글로 알려주시면 감사합니다! 😎

 

1. 리스트(List)

List: 리스트: 원소들 간의 순서 개념 O
      ex) (1, 2, 3) ≠ (3, 2, 1)
Set: 집합: 원소드 간의 순서 개념 X
     ex) {1, 2, 3} == {3, 2, 1}

• 리스트: 하나가 아닌 여러 개가 쭉 일렬로 나열되어 있는 것
  • 기본적인 연산: 삽입(insert), 삭제(remove), 검색(search)
  • 리스트를 구현하는 대표적인 두 가지 방법 - 배열, 연결 리스트
• 배열
  • 장점) 랜덤 액세스가 가능한 자료구조
    • 배열의 이름은 포인터 변수이고, 이 포인터 변수는 배열의 시작 주소를 가지고 있다.
    • 배열의 각 칸은 동일한 타입이다 → 배열의 각 칸은 크기가 동일하다.
    • 배열의 각각의 항목들이 연속적인 메모리를 차지한다.
      • 값을 저장할 뿐만 아니라 데이터들의 연속적인 순서까지 유지한다.
    • ⇒ 배열의 시작 주소 + 한 칸의 크기 x N = N 번째 칸의 주소에 접근 가능
      • N번 째 칸인지 M 번째 칸의 데이터를 읽든지 시간 상관이 없다.
  • 단점) 크기가 고정되어 있어 확장할 때 reallocation 필요.
             중간에 원소를 삽입하거나 삭제할 때 다수의 데이터를 옮겨야 함
• 연결 리스트
  • 장점) 길이의 제한이 없다.
             다른 데이터의 이동 없이 중간에 원소의 삽입, 삭제가 가능하다.
  • 단점) 랜덤 액세스 불가능

 

2. 연결 리스트(Liknked list)

배열: 배열의 각각의 항목들이 연속적인 메모리를 차지 
     → 값을 저장할 뿐만 아니라 데이터들이 연속적인 순서까지 유지할 수 있다.
연결리스트: 데이터의 순서 관계를 유지하기 위해서 반드시 순서대로 저장할 필요는 없다.

2-1. 노드

• 노드(node)
  • 연결 리스트는 노드들(데이터 + 다음 데이터의 주소)들이 링크로 연결되어 있는 자료구조
  • 노드는 데이터 필드와 하나 혹은 그 이상의 링크 필드로 구성
    • 데이터 필드: 연결 리스트에 저장할 데이터
    • 링크 필드: 다음 노드의 주소를 저장
      • 첫 번째 노드의 주소는 따로 저장해야 하고, 절대 잊어버려서는 안 된다.
      • 마지막 노드의 링크 필드는 NULL을 저장해서 연결 리스트의 끝임을 표시
• 노드의 삽입과 삭제
  

  

  • 다른 데이터의 이동 없이 중간에 원소의 삽입, 삭제가 가능하다.
  • 새로운 데이터를 아무 곳에나 저장한 후 → 원래 연결 리스트의 주소 값을 수정하면
    새로운 데이터를 중간에 삽입할 수 있다.
• 코드

  //연결리스트에서 하나의 노드르 표현하기 위한 구조체
  struct node{
    char *data;            //연결리스트에 저장할 데이터의 type 지정
                           //데이터 필드의 이름이 data
    struct node *next;     //다음 노드의 주소를 저장할 필드, 자기참조형 구조체
                           //링크 필드의 이름이 next
  }
  
  typedef struct node Node;
  Node *head = NULL;       //연결리스트의 첫 번째 노드의 주소를 저장할 포인터

  • 자기 참조형 구조체
    • 자신과 동일한 구조체에 대한 포인터를 멤버로 가진다라는 의미
    • struct node *next;
      • 포인터 변수의 type은 내가 가리키고 있는 객체의 type
        • *next는 struct node를 가리키고 있는 struct node type의 포인터 변수

 

 

 

 

---

부경대학교 권오흠 교수님의 [c로 배우는 자료구조 및 여러 가지 예제 실습] 강의 정리입니다. 감사합니다.

https://www.youtube.com/watch?v=eTwYE-ercNM