mini_me
우당탕탕 코드 프로젝트
mini_me
전체 방문자
오늘
어제
  • 분류 전체보기 (30)
    • 알고리즘 (4)
    • 자료구조 (5)
    • 운영체제 ( OS ) (7)
    • JSP (6)
    • 스프링 (5)

블로그 메뉴

  • 홈

공지사항

인기 글

태그

  • docker
  • 그리디 알고리즘
  • 자바스크립트
  • 알고리즘
  • Database 생성 및 권한
  • grafana
  • #연결리스트 #자료구조 #연결 리스트 #전공 공부
  • 연결리스트 # 열혈 자료구조 #자료구조
  • Greedy Algorithm
  • jenkins
  • ci/cd
  • load teet
  • 부하테스트
  • 데이터 모델링
  • K6
  • 자동화
  • Oracle Cloud
  • Clone Graph
  • 디렉티브 태그
  • 백엔드
  • graph algorithm
  • spanning tree
  • trie
  • smoke test
  • SQLD
  • dockerhub
  • 그래프 알고리즘
  • influxdb
  • mst
  • leetcode

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
mini_me
자료구조

[자료구조] 연결리스트- 변형된 원형 연결리스트

자료구조

[자료구조] 연결리스트- 변형된 원형 연결리스트

2021. 2. 2. 22:20

연결리스트 – 원형 연결리스트

 

원형리스트의 정의 및 특징

-       우리가 구현한 연결리스트의 (단순연결리스트) 마지막 노드 -> NULL 가르킴

그러면 그 마지막 노드가 첫번째 노드를 가리키게 하면 -> 원형 연결리스트!!

-       즉 마지막 노드가 첫번째 노드를 가르켜서 연결의 형태가 원을 이루는 형태

-       원형 연결 리스트에서는 머리와 꼬리의 구분이 없다고 얘기 가능

왜? 결국 두가지 경우 모두 8이 가리키는 건 1이다.

 

-       장점 : 머리,꼬리를 가리키는 포인터 변수를 각각두지 않아도 하나의 포인터 변수만 있어도 머리 , 꼬리에 노드를 간단히 추가 가능

 

변형된 원형 연결리스트

-       하나의 포인터 변수가 머리가 아닌 꼬리를 가리키게 한다면

새로운 노드가 추가 되었을 때 쉽게 추가가능

-       꼬리를 가리키는 포인터 변수? Tail

머리를 가리키는 포인터 변수? Tail -> next

 

변형된 연결리스트 구현

-       헤더파일

LFirst, LNext, LRemove 는 활용가치가 높은 함수들

이 중에서 LNext 함수 : 무한 반복 호출 가능, 리스트의 끝에 도달할 경우-> 첫번째 노드부터 다시 조회 시작

-       리스트의 초기화 및 노드의 삽입

리스트의 멤버들을 모두 0, NULL로 초기화시키기

void ListInit(List *plist)

{ plist->tail=NULL;

 plist->cur=NULL;

plist->before=NULL;

plist->NumofData=0;}

 

첫번째 노드의 추가

1.       Tail은 새노드를 가리켜야한다.

2.     새 노드도 자기자신을 가리켜야 한다

왜? 처음 추가 된 노드 = 머리이자 꼬리

3.      두번째 이후의 노드 추가

NewNode->next=plist->tail->next;

Plist->tail->next=newNode;

새 노드와 두번째 노드 연결

 

 

제일 먼저 추가된 노드와 새 노드 연결

 

 

-> 먼저 추가된 노드와 새롭게 추가된 노드를 연결

 

- LNext 함수

 LFirst 함수와 다른점 

 cur, before을 한칸씩 이동

 

- 노드 삭제

1. 삭제할 노드의 이전 노드가 삭제할 노드의 다음 노드를 가리키게 한다.

-삭제할 노드가 tail 가르킴 : tail의 이전 노드가 tail이 된다.

2. cur을 한칸 뒤로 이동

- 삭제할 노드가 리스트에 혼자 남는 경우 : NULL을 삭제

 

반응형

'자료구조' 카테고리의 다른 글

[자료구조]04. 연결리스트 - 연결리스트의 응용 (다항식)  (0) 2021.01.26
[자료구조]04.연결리스트 (2)- 단순 연결  (0) 2021.01.25
[자료구조]03. 연결 리스트-자료구조  (0) 2021.01.20
[자료구조]01. 알고리즘의 성능분석 방법 - 시간복잡도 / 공간복잡도  (2) 2021.01.13
    '자료구조' 카테고리의 다른 글
    • [자료구조]04. 연결리스트 - 연결리스트의 응용 (다항식)
    • [자료구조]04.연결리스트 (2)- 단순 연결
    • [자료구조]03. 연결 리스트-자료구조
    • [자료구조]01. 알고리즘의 성능분석 방법 - 시간복잡도 / 공간복잡도
    mini_me
    mini_me

    티스토리툴바

    개인정보

    • 티스토리 홈
    • 포럼
    • 로그인

    단축키

    내 블로그

    내 블로그 - 관리자 홈 전환
    Q
    Q
    새 글 쓰기
    W
    W

    블로그 게시글

    글 수정 (권한 있는 경우)
    E
    E
    댓글 영역으로 이동
    C
    C

    모든 영역

    이 페이지의 URL 복사
    S
    S
    맨 위로 이동
    T
    T
    티스토리 홈 이동
    H
    H
    단축키 안내
    Shift + /
    ⇧ + /

    * 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.