Python2 08일차 수업 정리_연결리스트 ADT, 필요연산, 단일 원형 연결리스트

- 연결리스트 ADT, 필요연산

- 단일 원형 연결리스트

 

---

- 연결리스트 ADT, 필요연산

 

연결리스트 ADT

- i번째 자리에 데이터 삽입 - i번째 자리에 데이터 삭제 - 데이터의 인덱스 반환 - 데이터 개수 반환 - 노드 총 개수 반환 - 연결리스트 비어있는지 확인 - 모든 노드 삭제 - 모든 노드의 데이터 출력

 

필요연산

insert(idx, x)	x를 연결리스트의 idx번째 요소로 삽입(맨앞자리는 0)
append(x)	x를 연결리스트의 맨 뒤에 삽입
pop(idx)	연결리스트의 idx번째 요소를 삭제하면서 알림
remove(x)	연결리스트에서 처음으로 나타나는 x를 삭제
get(idx)	연결리스트의 idx번째 요소를 알려줌
index(x)	요소 x가 연결리스트의 몇번째 요소인지 알려줌
isEmpty()	연결리스트가 빈 리스트인지 알려줌(True, False)
size()	연결리스트의 총 요소의 개수를 반환
clear()	연결리스트를 깨끗이 비워줌
count(x)	연결리스트에서 요소 x가 몇번 나타나는지 알려줌
extend(a)	연결리스트에서 나열할 수 있는  객체 a를 풀어서 추가함
copy()	연결리스트를 복사해서 새 연결리스트를 반환함
reverse()	연결리스트의 순서를 역으로 뒤집음
sort()	연결리스트 정렬함
=> 추가, 수정, 삭제, 검색, 총요소개수 확인, 총요소 출력 확인 (예제)

 

# LinkedList 클래스 : 연결리스트를 나타내는 클래스

class LinkedList :
    # Node 클래스 : LinkedList 클래스 내부에 Node 클래스 정의(내부 클래스)
    class Node :
        # Node클래스의 초기화 메소드
        def __init__(self, data = None, link = None) :
            # data, link 데이터 속성 초기화
            self.data = data
            self.link = link
    # LinkedList 클래스 초기화 메소드
    def __init__(self) :
        self.head = None
        self.length = 0
    
    # 확인용 출력 메소드
    def show(self) :
        current = self.head  #current라는 변수에 머리노드(처음노드)의 주소값 대입
        while current != None :
            print(current.data, end =" -> ")
            current = current.link #current에 다음노드 주소값 대입
        print() #줄바꿈

    # 데이터 삽입
    # 1) 맨앞에 삽입
    def insertFirst(self, data) :
        newnode = self.Node(data, self.head)
        self.head = newnode
        self.length += 1
    
    # 2) 맨뒤에 삽입
    def insertLast(self, data) :
        # 리스트에 요소가 하나도 없다면 맨앞에 삽입
        # insertFirst 메소드 호출
        if self.head == None : #머리노드(처음노드)가 비어있는지 확인 => 연결리스트가 비어있는지 확인
             self.insertFirst(data)
             return #함수종료
        
        # 리스트가 비어있지 않은 경우 기존에 마지막 노드를 찾아 새로운 노드를 추가
        current = self.head
        while current.link != None :
            current = current.link
        
        # 반복문을 다 돌고나면 current에는 기존의 마지막 노드가 담기게 됨
        # 추가할 노드 생성
        newnode = self.Node(data)
        # 기존의 마지막 노드에 새로추가한 노드 연결
        current.link = newnode
        # 연결리스트의 요소 1개 증가
        self.length += 1
    
    # 중간에 삽입
    def insert(self, idx, data) : #리스트의 특정 위치(idx)에 요소를 추가
        # idx 유효성 검사
        if idx < 0 or idx >= self.length :
            print("인덱스 범위 벗어남")
        # idx가 0이라면 맨 앞에 추가
        if idx == 0:
            self.insertFirst(data)
            return #함수종료
        
        # 삽입할 위치 이전 노드 찾기
        current = self.head
        for i in range(idx - 1) :
            current = current.link
        
        # 추가할 노드 생성
        newnode = self.Node(data, current.link)
        current.link = newnode
        self.length += 1
    
    # 데이터 삭제
    # 1) 맨 앞에 데이터 삭제
    def removeFirst(self) :
        # 연결리스트가 비어있는지 확인
        if self.head == None :
            print("비어있는 리스트")
            return #함수종료
        
        self.head = self.head.link
        self.length -= 1
    
    # 2) 중간 데이터 삭제
    def remove(self, idx) :
        # idx 유효성 검사
        if idx < 0 or idx >= self.length :
            raise IndexError("인덱스범위 벗어남") #raise 오류 강제 발생

        # idx가 0이라면 첫번째 데이데 삭제 메소드 호출
        if idx == 0 :
            self.removeFirst()
            return
        
        # 첫번째 인덱스가 아닌 데이터를 삭제
        current = self.head
        for i in range(idx) :
            prev = current #prev : 삭제할 노드의 이전 노드
            current = current.link #current : 삭제할 노드
        
        prev.link = current.link
        self.length -= 1

    # 데이터 수정
    def update(self, idx, data) : #해당 idx에 위차한 요소의 값 수정
        # idx 유효성 검사
        if idx < 0 or idx >= self.length :
            print("인덱스 오류")
            return # 함수 종료
        
        # idx 유효하다면
        current = self.head
        for i in range(idx) :
            current = current.link
        
        # current에는 해당 idx에 위치한 요소가 저장됨
        current.data = data
    
    # 검색
    def select(self, idx) : # idx에 위치한 data 반환
        # idx 유효성 검사
        if idx < 0 or idx >= self.length :
            print("인덱스 오류")
            return
        
        # idx 유효하다면
        current = self.head
        for i in range(idx) :
            current = current.link
        
        return current.data
    
    # 총 요소 개수 확인하는 메소드
    def size(self) :
        return f"현재 길이 : {self.length}"

li = LinkedList()

# 출력
li.show() #li는 비어있음

# 맨앞에 삽입
li.insertFirst(2)
li.show()
# 1 -> 2
li.insertFirst(1)
li.show()

# 맨뒤에 삽입 1 -> 2 -> 100
li.insertLast(100)
li.show()

# 중간에 삽입 1 -> 2 -> 3 -> 100
li.insert(2, 3)
li.show()

li.insert(3, 10)
li.insertLast(200)
li.show()

# 맨앞에 삭제 2 -> 3 -> 10 -> 100 -> 200 -> 
li.removeFirst()
li.show()

# 중간에 삭제 2 -> 3 -> 10 -> 200 -> 
li.remove(3)
li.show()
li.remove(3) #2 -> 3 -> 10
li.show()

# 데이터 수정 # 2 -> 5 -> 10
li.update(1, 5)
li.show()

# 검색
print(f"0번째 인덱스의 값은 : {li.select(0)}")
print(f"2번째 인덱스의 값은 : {li.select(2)}")

# 총요소개수 확인
print(li.size())

 

2 -> 

1 -> 2 ->

 1 -> 2 -> 100 -> 

1 -> 2 -> 3 -> 100 -> 

1 -> 2 -> 3 -> 10 -> 100 -> 200 -> 

2 -> 3 -> 10 -> 100 -> 200 -> 

2 -> 3 -> 10 -> 200 ->

 2 -> 3 -> 10 -> 

2 -> 5 -> 10 -> 

0번째 인덱스의 값은 : 2 

2번째 인덱스의 값은 : 10 

현재 길이 : 3

 

리스트와 연결리스트 비교

---

- 단일 원형 연결리스트

단일 원형 연결리스트란 : 

단순 연결리스트의 마지막 노드가 다시 첫번째 노드를 가리키도록 

설정되어 리스트의 형태가 원형(circle)형태로 구성되어

계속 회전하면서 연속으로 찾아 갈 수 있음

 

단순 원형 연결리스트

# 노드 생성
class Node :
    def __init__(self) :
        self.data = None
        self.link = None

node1 = Node()
node1.data = "짱구"
node1.link = node1

# print(node1.data)
# print(node1)
# print(node1.link)

# node2 철수
# 노드 연결
node2 = Node()
node2.data = "철수"
node1.link = node2
# 마지막노드 -> 첫번째 노드
node2.link = node1

# node3 훈이
node3 = Node()
node3.data = "훈이"
node2.link = node3
node3.link = node1

# node4맹구
node4 = Node()
node4.data = "맹구"
node3.link = node4
node4.link = node1

# 반복문
current = node1
print(current.data, end =" -> ")
while current.link != node1 : #한 바퀴를 모두 도는 동안
    current = current.link
    print(current.data, end =" -> ")
    
# 마지막 노드에 유리 데이터 추가
newnode = Node()
newnode.data = "유리"
node4.link = newnode
newnode.link = node1

# 출력
current = node1
print(current.data, end =" -> ")
while current.link != node1 :
    current = current.link
    print(current.data, end = " -> ")
    
# 마지막 노드 삭제
current = node1
while current.link.link != node1 :
    current = current.link
# print(current.data)
current.link = node1

# 출력
current = node1
print(current.data, end = " -> ")
while current.link != node1 :
    current = current.link
    print(current.data, end =" -> ")

짱구 -> 철수 -> 훈이 -> 맹구 -> 
짱구 -> 철수 -> 훈이 -> 맹구 -> 유리 -> 
짱구 -> 철수 -> 훈이 -> 맹구 -> 

 

 

2024.02.20