연결리스트

Linked 리스트의 기본구조에 대해서 알아보자!

각 연결리스트는 Node로 구성되어있고, Node안에는 data와 link로 구성되어있다.
안에 들어있는 data는 그림에 나와있는 정수형 말고도 문자, 레코드 등 여러 구조가 가능하다.

Node를 코드로 구성해보면 다음과 같다.

class Node:
	def __init__(self, item):
    	self.data = item # data
        self.next = None # next link (다음 인자를 가리킨다.)

여기서 next는 다음 노드에 접근하는 방법이다.

P.head == a
a.next == b
b.next == c

또한, 연결리스트에서 중요한 속성은 크게 셋으로 나뉜다.

Head
Tail
*Number of Nodes

class LinkedList:
	def __init__(self):
    	self.nodeCount = 0
        self.head = None
        self.tail = None

연결리스트의 연산 정의

연결리스트의 연산은 크게 특정 원소 참조, 순회, 원소 삽입, 삭제, 연결이 있다.

• 특정 원소를 참조할 때
  pos번째의 node를 가리키고 싶을 때 쓰는 메서드이다.

def getAt(set, pos):
	if pos <= 0 or pos > self.nodeCount:
    	return None  #특정 경우 제외
    i = 1
    curr =  self.head # 연결리스트의 첫번째 노드

    # 앞에서부터 하나하나 탐색하기 때문에 선형탐색과 유사
    while i<pos:
    	curr = curr.next
        i += 1
    return curr

단, pos의 예외 범위를 if로 지정해줘야한다!

• 리스트를 순회할 때

연결리스트에 들어있는 data를 리스트의 요소로 하나하나 append하고, 최정 리스트를 반환한다. 주의해야 할 점은, 리스트 안에 append 되어야 할 것이 node 자체가 아니라 node안의
data라는 것이다!

def traverse(self):
	t_list = []
    curr_node = self.head # 첫 노드에 접근

	while curr_node != None # tail이 되면 none이 됨
    	t_list.append(curr_node.data) # 노드가 아니라 item을 넣음
    	curr_node = curr_node.next # 다음 노드에 접근

	return t_list 

• 원소 삽입

연결리스트의 pos 위치에 원소를 삽입하는 기본 코드는 다음과 같다.
마지막에 nodeCount는 1을 더해준다!

def insertAt(self, pos, newNode):
	prev = self.getAt(pos-1) # post 이전의 노드를 prev로 설정
   	newNode.Next = prev.next
    prev.next = nextNode
    self.nodeCount += 1

근데 위 코드에는 예외 처리가 필요하다. 왜냐하면 삽입 위치가 맨 앞, 맨 끝일대를 처리하지 못하기 때문이다. 그래서 head와 tail을 따로 조정해주는 코드가 필요하다!

def insertAt(self, pos, newNode):
	# pos 예외 범위 지정
    if pos<1 or pos>self,nodeCount:
    	return False

	# 리스트 맨 앞 삽입할 때
    if pos==1:
    	newNode.next = self.head # 기존 head가 newNode의 next로 밀려남
        self.head = newNode
    else:
    	prev = self.getAt(pos-1) # post 이전의 노드를 prev로 설정
        newNode.next = prev.next
        prev.next = nextNode

    # 리스트 맨 뒤 삽입할 때
    if pos==self.nodeCount +1:
    	self.tail = newNode

    self.nodeCount += 1
    return True

하지만 여기서 tail을 찾으려면 앞에서부터 차근차근 찾아야한다.
그럼 선형 배열과 비슷한 복잡도가 발생하므로, 비효율적일 수 있다!
따라서 다음과 같이 코드를 수정해볼 수 있다.

def insertAt(self, pos, newNode):
	if pos<1 or pos>self.nodeCount:
    	return False

	if pos==1:
    	newNode.next = self.head
        self.head = newNode

	# prev를 미리 지정
    else:
    	if pos == self.nodeCount +1:
        	prev = self.tail
        else:
        	prev = self.getAt(pos-1)

		newNode.next = prev.next
        prev.next = newNode


	if pos == self.nodeCount + 1:
    	self.tail = newNode

	self.nodeCount += 1
    return True   

이전 코드의 else: 부분을 tail일때와 tail이 아닐때로 나누어 tail연산이 구분되어 일어나도록 한다.

• 이때 연결리스트의 원소 삽입 복잡도는 다음과 같다.
  맨 앞 삽입 : O(1)
  중간 삽입 : O(n)
  맨 끝 삽입 : O(1) # tail 포인터 때문
  

• 원소 삭제

pos 위치에서 pop을 하면, 그 데이터를 리턴하게 한다.
기본 코드는 다음과 같다.

def popAt(self, pos):
	if pos<1 or pos>self.nodeCount:
    	raise IndexError

    curr = self.getAt(pos) #제거할 node
    prev = self.getAt(pos-1) #이전 node

	prev.next = self.getAt(pos+1)
    self.nodeCount -= 1
    return curr.data

하지만 위 코드에도 예외 처리를 해줘야한다.
역시 맨 앞, 맨 뒤를 제거할 때 유일한 리스트 원소를 제거할 때를 처리하지 못한다!
해결 방법은 다음과 같다.

def popAt(self, pos):
    if pos<1 or pos>self.nodeCount:
        raise IndexError

    curr = self.nodeCount == 1 & pos ==1: # 유일한 리스트
        self.head = None
        self.tail = None

    elif pos == 1: # 유일하지 않지만 맨 앞 삭제
        self.head = self.getAt(pos+1)

    else:
        prev = self.getAt(pos-1)

    if self.nodeCount != pos: # 맨 뒤가 아닐 때
        prev.next = self.getAt(pos+1)
    else:
        self.tail = prev
        prev.next = None

self.nodeCount -= 1
return curr.data

• 두 리스트 연결

#L : 이어붙일 리스트
def concat(self. L):
    self.tail.next = L.head # 원래 리스트의 맨 끝이 이어붙일 리스트의 처음

    # L에 주어진 리스트가 빈 리스트일 때 예외처리

    if L.tail:
        self.tail = L.tail # 내 원래 tail을 이어붙인 리스트의 tail로 가게함

    self.nodeCount += L.nodeCount # count 두개를 합한 만큼