LinkedList
LinkedList는 선형 데이터 구조의 한 종류. 데이터들이 순서대로 쭉 늘어선 것이 아니라 자료의 주소값으로 서로 연결되어 있는 구조를 하고 있음. 서로 연결된 노드들의 집합이라 표현할 수 있는데 노드에는 데이터와 다른노드와 연결하는 링크를 포함하고 있다. 이때 첫번째 노드를 헤드(Head), 마지막 노드를 테일(Tail)이라고 함.
- 단일 연결 리스트(Singly Linked List) : 각 노드가 다음 노드만을 가리키는 가장 단순한 형태의 연결리스트. 각 노드에 자료공간과 한개의 포인터공간이 있음.
- 이중 연결 리스트(Doubly Linked List) : 각 노드가 이전 노드와 다음 노드 양쪽을 가리키는 구조로, 양방향 탐색이 가능함. 자료공간과 다음노드를 가리키는 Next 공간, 이전노드를 가치키는 Prev 공간이 있음.
Python에는 기본적으로 LinkedList구조를 직접적으로 제공하는 내장 자료형은 없다. Node 클래스를 사용하여 링크된 목록을 만들게됨.
단일연결리스트
Node Class 생성
class Node:
def __init__(self, data):
self.data = data
self.next = NoneHead에 노드 삽입
def insertAtBegin(self, data):
new_node = Node(data) # 입력받은 데이터로 Node클래스의 새 인스턴스 생성. 이 노드의 next속성은 기본적으로 None
if self.head is None: # 만약 연결리스트가 비어있다면, 새 노드가 첫번째 노드가 됨.
self.head = new_node # self.head를 새 노드로 설정.
return
else: # 이미 head가 있다면
new_node.next = self.head # 새 노드의 next를 head로 설정. 새 노드가 현재 연결리스트의 첫번째 노드를 가리키도록 함.
self.head = new_node # 새노드가 head가 됨.위의 과정을 통해 새 데이터가 연결리스트의 맨 앞에 삽입됨.
특정 위치에 노드 삽입
def insertAtIndex(self, data, index):
new_node = Node(data) # 입력받은 데이터로 Node클래스의 새 인스턴스 생성. 이 노드의 next 속성은 기본적으로 None.
current_node = self.head # 현재노드를 head로 설정.
position = 0 # head의 인덱스는 0
if position == index: # 삽입하려는 위치가 맨 앞이라면
self.insertAtBegin(data) # 위의 헤드에 삽입하는 메소드를 호출
else: # 연결리스트의 중간 또는 끝부분에 삽입이라면
while(current_node != None and position+1 != index): # 연결리스트의 끝이 아니고 새 노드가 삽입될 위치의 바로 이전노드를 찾을때까지 순회.
position = position+1 # current_node의 인덱스 추적.
current_node = current_node.next # current_node의 다음 노드를 연결하며 이동.
if current_node != None: # 만약 연결리스트의 끝이아니고 인덱스의 이전노드까지 도달했다면.
new_node.next = current_node.next # 새 노드의 next는 current_node의 다음 노드.
current_node.next = new_node # current_node의 다음노드는 새 노드. current_node -> new_node(삽입!) -> current_node_next
else: # 설정한 인덱스가 연결리스트의 범위를 벗어난다면
print("Index not present")Tail에 노드 삽입
def inserAtEnd(self, data):
new_node = Node(data) # 입력받은 데이터로 Node클래스의 새 인스턴스 생성. 이 노드의 next 속성은 기본적으로 None.
if self.head is None: # 만약 head가 없다면. 연결리스트가 비어있다면
self.head = new_node # 새 노드를 연결리스트의 head로 설정.
return
current_node = self.head # current_node가 헤드노드.
while(current_node.next): # current_node의 next가 있으면
current_node = current_node.next # current_node는 next노드로 설정.
current_node.next = new_node # next가 없을때까지 while문 돈 후, next가 없으면 새 노드를 current_node의 next로 설정. current_node -> current_node.next(new node!)노드의 값을 update
def updateNode(self, value, index):
current_node = self.head # current_node가 head
position = 0 # head의 인덱스는 0
if position == index: # head의 값을 바꾸는거면
current_node.data = value # current의 data를 입력한 value로 입력.
else: # 중간, 끝에 인덱스를 업데이트 하는 경우.
while(current_node != None and position != index): # current_node가 연결리스트의 끝이 아니고 현재 위치가 업데이트하려는 인덱스와 다르면
position = position+1 # current_node의 위치 추적
current_node = current_node.next # current_node의 다음노드로 이동
if current_node != None: # current_node가 끝이 아니고 현재 위치가 업데이트하려는 인덱스에 도달했다면
current_node.data = value # current_node의 값을 value로 입력.
else: # 인덱스에 도달하지 못하고 끝에 왔다면
print("Index not present") # 인덱스가 연결리스트의 범위에 없음.첫번째 노드 제거
def remove_first_node(self):
if(self.head == None): # 연결리스트가 비어있다면 제거할 필요없어서 아무런 작업 수행없이 반환.
return
self.head = self.head.next # head의 next 노드를 새head로 만듬.맨 끝 노드 제거
def remove_last_node(self):
if self.head is None: # 연결리스트가 비어있다면 제거할 필요없어서 아무런 작업 수행없이 반환.
return
if self.head.next is None: # 노드가 1개만 있다면
self.head = None # head를 None으로 설정하여 연결리스트를 비움.
return
current_node = self.head # current_node가 헤드로 설정.
while(current_node.next.next): # current_node의 다음다음노드가 None이 아니라면. 연결리스트의 마지막에서 두번째 노드 찾기(tail의 전 노드 찾기).
current_node = current_node.next # current_node가 다음노드로 이동.
current_node.next = None # 연결리스트의 마지막에서 두번째 노드의 next는 None으로 설정.특정 위치의 노드 제거
# Method to remove at given index
def remove_at_index(self, index):
if self.head == None: # 리스트가 비어있을 경우. 제거할 노드가 없으서 그대로 반환.
return
current_node = self.head # head 노드에서 시작
position = 0 # current_node 위치 추적
if position == index: # 만약 첫번째 노드를 제거하려면
self.remove_first_node() # 위의 메소드 호출.
else:
while(current_node != None and position+1 != index): # current_node가 끝이 아니고, 입력한 인덱스의 전 인덱스 찾기.
position = position+1 # current_node의 위치 추적
current_node = current_node.next # current_node를 다음노드로 설정
if current_node != None: # 제거하려는 노드의 이전노드에 도달했다면
current_node.next = current_node.next.next # current_node의 다음노드는 current_node의 다음다음노드. current_node -> current_node.next(인덱스!삭제!) -> current_node.next.next
else: # 주어진 인덱스에 도달하지 못하고 연결리스트의 끝에 도달햇다면 범위에서 벗어남.
print("Index not present")주어진 데이터가 있는 노드 제거
def remove_node(self, data):
if not self.hesd: # 리스트가 비어있다면 작업수행 x.
return
current_node = self.head # head에서 시작
if current_node.data == data: # head가 주어진 data를 가지고 있는지 확인
self.remove_first_node() # 주어진 데이터를 가지고 있으면 위의 메소드를 이용해서 head 제거
return
while current_node is not None and current_node.next.data != data: # current_node가 끝이 아니고, current_node의 다음노드가 data를 가지고 있지 않으면. 같은 data를 가지고 있는 node의 직전의 노드를 찾기 위함.
current_node = current_node.next # current_node를 다음노드로 설정
if current_node is None: # 연결리스트의 끝까지 도달했으나 데이터를 찾지 못한 경우
return
else:
current_node.next = current_node.next.next # 다음 노드를 건너뛰어 삭제. current_node -> current_node.next(인덱스!삭제!) -> current_node.next.next연결리스트 모든 노드의 data 출력
def printLinkedList(self):
current_node = self.head # current_node를 head로 설정
while(current_node): # 연결리스트의 끝에 도달할때까지
print(current_node.data) # 노드의 data출력
current_node = current_node.next # current_node를 다음노드로 설정연결리스트의 길이 반환
def sizeOfLL(self):
size = 0 # 노드의 수 카운트.
if(self.head): # head의 존재여부 확인.
current_node = self.head # current_node가 head부터 시작
while(current_node): # 연결리스트의 끝에 도달할때까지
size = size+1 # 순회할때마다 size를 1씩 증가
current_node = current_node.next # current_node를 다음노드로
return size
else: # head가 없다면. 빈 연결리스트라면.
return 0추가 공부할것.
- 이중연결리스트 코드
- 연결리스트의 장점 중 하나가 미리 데이터의 크기를 지정하지 않아도 되는 점인데, 파이썬은 이미 동적배열을 구현하고 잇어서 리스트의 길이를 지정하지 않아도 되니깐 연결리스트의 다른 장점이 있는지 공부하기.
- LinkedList vs Array
