[python_dataStructure] 4. 단순연결리스트

🧩 단순연결리스트(SinglyLinkedList) : 데이터 → 순서를 보장한 상태에서 저장하는 자료구조

• 메모리 저장공간 비연속적 🚨
  • But, 데이터와 데이터를 연결 ➡️ 순차적저장 ✅
• 미리 저장공간 정해져있지 않음 ⛔️
  • 데이터 추가 및 삭제 → 메모리공간으로 효율적관리 가능 ✅

📎 선형리스트와 단순연결리스트 비교

구분	특징	의미
선형리스트 (도서관장서)	① 책장의 용량이 한정적	→ 미리 저장공간 정해져있음 ⛔️
	② 책의 청구기호로 빠르게찾기 가능	→ 인덱싱기능
	③ 새로운장서가 들어오면 나머지 책 밀어내기함	→ 새로운공간 확보 후, 밀어내기
단순연결리스트(온라인강의수강생)	① 수강생규모가 한정적 ❌	→ 미리 저장공간 안정해져있음 ✅
	② 수강신청정정으로 추가 및 삭제 가능	→ 추가 및 삭제 효율적
	③ 출석정보조회를 위해 전체정보검색	→ 인덱싱기능 ❌

---

1 단순연결리스트 형태

1. 데이터가 다음 데이터위치를 저장함
2. 데이터 + 다음데이터주소값 → 저장

📍 head : 단순연결리스트의 첫번째 노드가 무엇인지 의미하는 정보
📍 노드 : 데이터(item) + 링크(reference)
📍 데이터 : 항목. 노드값이 저장됨
📍 링크 : 메모리주소. 다음 노드 위치를 알려줌

---

2 단순연결리스트 특징

1. 노드 → 물리적으로 떨어진곳에 위치함
2. 각 노드 주소값 → 순차적 ❌
3. 저장공간 미리 지정 ⛔️
4. 데이터 추가 및 삭제에 용이
   • 선형리스트 : 기존데이터 위치 재조정 → 오버헤드발생 🚨
5. 특정데이터검색 → 비효율적
   • 첫 노드 ~ 목표 노드까지 순차탐색

---

3 단순연결리스트 구현

1️⃣ 노드의 정의

>>> class Node(): # Node 데이터형 정의 -> class 사용
		def __init__(self): # class 생성자
        	self.data = None # 데이터공간
            self.link = None # 링크공간

📍 1. 서울 노드정의
>>> node1 = Node() # 객체생성
>>> node1.data = "서울" # 생성자값주입

📍 2. 대구 노드정의
>>> node2 = Node() # 객체생성
>>> node2.data = "대구" # 생성자값주입
>>> node1.link = node2 # node1 링크 연결

📍 3. 부산 노드정의
>>> node3 = Node() # 객체생성
>>> node3.data = "부산" # 생성자값주입
>>> node2.link = node3 # node2 링크 연결

2️⃣ 데이터가 3개인 단순연결리스트 출력(탐색)

📍 단순연결리스트 출력
	# Link.link•••로 데이터 뽑아냄
>>> print(node1.data, end = '')
>>> print(node1.link.data, end = '')
>>> print(node1.link.link.data, end = '')

---

4 단순연결리스트 탐색함수

1️⃣ 첫번째 노드를 현재(Current)노드로 지정

2️⃣ 링크가 가리키는 다음노드를 현재노드로 지정

• 현재 노드 링크가 비어있지 않다는 가정

3️⃣ 현재노드 링크가 비어있으면 종료

• 2단계 계속 반복

4️⃣ 코드구현

📍 단순연결리스트 탐색함수
>>> current = node1 # 첫번째노드 -> 현재노드로 지정
>>> print(current.data, end = '')

	# current 링크가 없을때까지 반복
>>> while current.link != None:
		# 현재노드의 다음노드 -> current로 지정
		current = current.link
        print(current.data, end = '')

---

5 단순연결리스트 일반적형태

• Head : 첫번째 노드
• Current(현재) : 현재 처리중인 노드
• Pre(이전) : 현재 처리중인 앞 노드

---

6 단순연결리스트 데이터삽입(중간)

1️⃣ Current, Pre 이동

• 데이터를 끼워 넣고자 하는 2개의 노드를 찾을 때까지
  ➡️ Current, Pre 이동
  

2️⃣ Pre노드 링크 → 새로운노드

• Pre 노드의 링크가 새로운 노드를 가리키게 함

3️⃣ 새로운노드 링크 → Current

4️⃣ 코드구현

📍 단순연결리스트 데이터삽입(중간)
>>> current = head # current 제일 처음부터 시작

>>> while 마지막노드까지:
		pre = current # pre노드 -> 한칸씩이동
        current = current.link # current노드 -> 한칸씩이동
        
        if current.data == "부산":
        	node = Node() # 새로운노드 생성
            node.data = "포항" # 새로운노드 생성자주입
            
            # 새로운 노드 연결
            node.link = current
            pre.link = node

---

7 단순연결리스트 데이터삽입(첫번째)

1️⃣ 추가데이터 생성 → 링크를 기존의 Head로 지정

2️⃣ 코드구현

📍 단순연결리스트 데이터삽입(첫번째)
>>> newNode = Node() # 새로운노드(객체)생성
>>> newNode.data = "파주" # 새로운노드 생성자주입

>>> newNode.link = Head # 새로운노드 링크 -> 기존 Head에 연결
>>> Head = newNode # 새로 Head 재지정

---

8 단순연결리스트 데이터삽입(마지막)

1️⃣ 추가데이터 생성 → 마지막 데이터 링크를 추가데이터로 지정

2️⃣ 코드구현

📍 단순연결리스트 데이터삽입(마지막)
>>> current = 마지막노드
>>> node = Node() # 새로운노드(객체)생성

>>> node.data = "제주" # 새로운노드 생성자주입
>>> current.link = node # 마지막노드링크 -> 새로운노드

---

9 단순연결리스트 데이터삭제(첫번째)

1️⃣ Current노드, Head 동시에 첫번째 가리킴

2️⃣ Head노드 → 다음노드로 이동, Current 삭제

3️⃣ 코드구현

📍 단순연결리스트 데이터삭제(첫번째)
>>> current = head # 동시에 가리킴
>>> head = head.link # 헤드 -> 두번째로 옮김

>>> del(current) # 첫번째 노드 삭제

---

10 단순연결리스트 데이터삭제(지정)

1️⃣ 동작순서

• 삭제할 데이터 → Current노드로 지정
• Pre노드 링크 → Current노드 링크로 지정
• Current 노드 삭제

2️⃣ 코드구현

📍 단순연결리스트 데이터삭제(지정)
>>> current = head # 동시에 가리킴
>>> while 마지막노드까지:
		pre = current
        current = current.link # 한칸씩 이동
        
        if current.data = "대구": # 원하는노드에 도착
        	pre.link = current.link # 이전과 이후 연결
            del(current)

---

11 노드검색

1️⃣ 동작순서

• 현재노드 → 첫번째노드로 지정 (Head)
• 현재노드 → 검색할 데이터와 일치 ➡️ 반환

2️⃣ 코드구현

📍 노드검색
>>> current = head
>>> if current.data = "대구"
		return current

>>> while current.link != None:
		current = current.link
        
        if current.data = "대구"
        	return current
    
    return Node() # 빈 노드 반환

---

12 시간복잡도

항목	조회	삽입	삭제
선형리스트	O(1)	O(n)	O(n)
단순연결리스트	O(n)	O(1)	O(1)

---