연결 리스트 (Linked Lists)

연결리스트와 선형 배열의 차이

데이터 원소등를 순서를 지어 늘언호는 점에서는 연결리스트와 선형배열이 비슷하지만, 데이터 원소들을 늘어놓는 방식에서 차이가 있다. 선형 배열은 번호가 붙여진 칸에 원소들을 채워넣는 방식인 반면, 연결리스트는 각 원소들을 줄줄이 엮어서 관리하는 방식이다.

 

연결리스트

연결리스트 기본 구조

장점

연결리스트에서는 원소들이 링크(Link)라고 부르는 고리로 연결되어 있는데,  67에서 34를 가리키는 고리를 자르고, 58로 이어붙이면서 34를 삭제하거나, 67이 34가 아닌 다른 원소에 연결하여 삽입하는것이 배열보다 빠른시간 내에 처리 할 수 있다. 이러한 이점 때문에, 원소의 삽입/삭제가 번번히 일어나는 응용에서는 연결리스트가 많이 이용된다.

 

단점

원소의 삽입과 삭제가 용이하다는 장점도 있지만, 연결리스트의 단점 중 한가지는 저장공간 소요가 크다는 점이다.

연결리스트를 구성하는 Node에는 DATA와 다음을 가리키는 Link를 담고 있기 때문에 동일한 데이터원소를 담기 위해서 사용하는 메모리가 크기 때문이다.

그리고 원소를 찾아가는데에는 선형 배열의 경우보다 시간이 더 오래걸린다. 선형배열은 번호가 붙여진 칸에 원소가
들어가 있으므로, 그 번호를 이용하여 단번에 찾아갈 수 있지만, 링크드리스트는 고리로 연결된 모습을 하고있음으로,
특정 번째의 원소를 찾으려면 하나씩 찾아가야한다.

 

연결리스트 파이썬 구현

1) Node 생성

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None


# Node 생성
node1 = Node(1)
node2 = Node(3)
node1.next = node2

# Node 출력
print("node1 data : ", node1.data) # node1 data :  1
print("node1 next.data : ", node1.next.data) # node1 next.data :  3
print("node2 data : ", node2.data) # node2 data :  3

 

1. Class Node 클래스는 노드들의 정보를 기록하여 생성하는 클래스이다.
2.  self.next 속성으로 다음 노드가 무엇인지 알 수 있다.

 

2) Node 삽입

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail
	
    
    def getAt(self, pos):
		if pos < 0 or pos > self.nodeCount:
			return None

		i = 0
		curr = self.head
		while i < pos:
			curr = curr.next
			i += 1

		return curr

	def insertAfter(self, prev, newNode):
		newNode.next = prev.next
		if prev.next is None:
			self.tail = newNode
		prev.next = newNode
		self.nodeCount += 1
		return True


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

		if pos != 1 and pos == self.nodeCount + 1:
			prev = self.tail
		else:
			prev = self.getAt(pos - 1)
		return self.insertAfter(prev, newNode)
        
        
# Node 생성
node1 = Node(1)
node2 = Node(3)
node3 = Node(8)


# Linked List 생성
link = LinkedList()
link.insertAt(1, node1)
link.insertAfter(node1, node2)

1. LinkedList
   1. nodeCount 속성은 LinkedList의 총길이를 뜻한다.
   2. head 속성은 LinkedList 맨 앞을 뜻한다.
   3. tail 속성은 LinkedList 맨 뒤를 뜻한다.
2. getAt() 함수는 pos번째 위치의 node를 반환한다.
   1. pos가 0보다 작거나, 총개수보다 많으면 None을 반환한다.
   2. while문을 돌며, pos번째까지 반복한다.
3. insertAt() 함수는 정해진 곳에 node를 삽입한다.
   1. insertAt()은 pos번째가 1보다 작거나, node의 총 개수+1보다 많으면 False를 반환한다.
   2. pos가 1이아니거나, pos가 총개수+1과 같으면 LinkedList 마지막을 뜻하는 self.tail을 prev변수에 넣어준다.
   3. 모든 조건이 아니면, getAt()을 통해 현재위치-1(prev는 이전을 뜻함, insertAfter에서 pos가 아닌 prev를 필요로하기때문에 -1을 한다.)
4. insertAfter() 함수는 insertAt에서 결과를 반환한 node를 삽입한다.
   1. Node가 1 -> 2 -> 3 일 때, 2뒤에 삽입할 때는 먼저, 새로운 노드가 3을 가르키게한다.(newNode = prev.next)
   2. 만약 next를 통해 노드가 없다면 새로운 노드는 LinkedList의 마지막이 된다.
   3. 그리고 2 -> (NewNode) -> 3이 되도록 2가 NewNode를 가르킬 수 있도록 한다.

 

3) Node 출력 

class Node:
    def __init__(self, item):
        self.data = item
        self.next = None


class LinkedList:

     ㆍㆍㆍ
     
     def traverse(self):
        result = []
        curr = self.head
        while curr.next:
            curr = curr.next
            result.append(curr.data)
        return print(result)


        

link.traverse() # 결과 : [1, 3]

1. traverse() 함수를 통해 전체 LinkedList를 출력한다.
   1. LinkedList의 처음인 head부터 다음 노드를 가르키는 것을 반복하여 리스트에 넣어 출력한다. 

 

4) Node 삭제

Class LinkedList:
	
    ㆍㆍㆍ
    
    def popAfter(self, prev):
        if prev == self.tail:
            return None
        curr = prev.next
        prev.next = curr.next
        if curr.next == None:
            self.tail = prev
        self.nodeCount -= 1
        return curr.data


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


link.popAt(1)
link.traverse() # 결과 : 8

1. popAt() 함수에서 삭제할 pos번째를 받아 삭제한다.
   1. pos가 LinkedList의 범위를 벗어나면 IndexError가 나타난다.
   2. getAt()을 통해 현재위치-1(prev는 이전을 뜻함, popAfter에서 pos가 아닌 prev를 필요로하기때문에 -1을 한다.)
2. popAfter()함수에서 popAt()에서 넘겨받은 값을 삭제한다.
   1. Node가 1 -> 2 -> 3 일 때, 2를 제거한다면, 먼저 삭제하려는 현재를 위치를 찾는다. (curr = prev.next)
   2. prev.next를 이용해 현재 노드의 다음을 가르킨다. (prev.next = curr.next)
   3. curr.next가 없다면 클래스의 생성자인 tail에 prev를 넣고, 총개수-1을 해준다.