연결 리스트 (Linked List)

추상적 자료구조 (Abstract Data Structures)

자료구조의 내부 구현을 숨겨두고 밖에서 보이는 것들 (두 가지)을 말함

• Data : 정수, 문자열, 레코드...
• A set of operations : 삽입, 삭제, 순회... 정렬, 탐색...

 

 

 

 

---

기본적 연결 리스트

앞에 있는 놈이 뒤에 있는 놈을 가르키는 형식으로 늘어놓은 것이 연결 리스트라고 한다.

리스트의 맨 처음 노드 Head

리스트의 맨 마지막 노드 Tail

리스트에 노드를 추가할 때 Tail을 사용한다.

노드가 몇개 있는지도 기록해두는 것이 좋다 of nodes : 3

 

노드는 Data와 Link(Next)를 가지고 있다.

노드 내의 데이터는 다른 구조로 이루어질 수 있다 (문자열, 레코드, 또 다른 연결 리스트 등)

 

 

 

 

---

자료구조 정의

# Node 클래스

# Node 클래스
class Node:
    # 생성자
    def __init__(self, item):
        self.data = item
        self.next = None

 

 

# LinkedList 클래스

# LinkedList 클래스
class LinkedList:
    def __init__(self):
        self.nodeCount = 0
        self.head = None
        self.tail = None

 

 

 

 

---

연산정의

1. 특정 원소(k번째) 참조
2. 리스트 순회
3. 길이 얻어내기
4. 원소 삽입
5. 원소 삭제
6. 두 리스트 합치기

 

 

1. 특정 원소 참조 getAt

노드를 0부터 참조하지 않고 1부터 참조하는 이유는 나중에 0을 다른 목적으로 사용하기 위해서이다.

    # 1. 특정 원소 참조
    def getAt(self, pos):
        # 특정위치가 0보다 작거나 노드의 길이보다 크면 None을 반환
        if pos <= 0 or pos > self.nodeCount:
            return None
        
        i = 1
        curr = self.head # 연결리스트의 첫번째 노드를 가르킴
        
        # i가 pos보다 작은 동안에 i를 하나씩 증가시키면서 curr를 curr의 next를 가르키게 한다
        # 즉 pos-1번 만큼 전진하면 그때 curr가 가르키는 것이 내가 리턴하려는 pos번째 노드가 된다
        while i < pos: 
            curr = curr.next
            i += 1
        
        return curr

 

 

 

배열과 비교한 연결 리스트

선형 배열은 "번호가 붙여진 칸에 원소들을 채워넣는" 방식이라고 한다면, 연결 리스트는 "각 원소들을 줄줄이 엮어서" 관리하는 방식이다.

선형 배열에 비해 연결 리스트가 가지는 이점은?

연결 리스트에서는 원소들이 링크(link)라고 부르는 고리로 연결되어 있으므로, 가운데에서 끊어 원소 하나를 삭제하거나, 삽입하는 것이 선형 배열의 경우보다 빠른 시간내에 처리할 수 있다. 따라서 원소의 삽입/삭제가 빈번히 일어나는 응용에서 연결 리스트가 많이 이용된다. 컴퓨터 시스템을 구성하는 중요한 요소인 운영체제(operating system)의 내부에서도 이러한 연결 리스트가 여러 곳에서 이용되고 있다.

 

그렇다면 단점은?

선형 배열에 비해서 데이터 구조표현에 소요되는 저장 공간(메모리) 소요가 크다. 또 "k번째 원소"를 찾아가는데 선형 배열보다 오랜시간이 걸린다. (앞에서부터 특정원소까지 하나씩 링크를 따라가며 찾아야 하니까)

 

 

 

2. 리스트 순회

    # 2. 리스트 순회
    def traverse(self):
        result = []
        curr = self.head
        while curr is not None:
            result.append(curr.data)
            curr = curr.next
        return result

 

 

 

3. 연결 리스트 연산 - 원소의 삽입

원소가 삽입될 수 있는 조건 1 <= pos <= nodeCount + 1 이 범위 안에만 삽입할 수 있다.

newNode를 삽입하고 성공/실패에 따라 True/False를 리턴한다.

먼저 pos-1을 찾아낸 후 prev에 저장

첫번째 newNode의 뒷쪽 링크를 조정

두번째 : 앞선 노드 pos-1번째 노드가 new노드를 가르키도록 하게한다

마지막으로 노드카운트를 1만큼 증가시킨다.

첫번째와 두번째의 순서를 바꾸면 안된다.

 

코드 구현시 주의사항

1. 삽입하려는 위치가 리스트 맨 앞일 때

• prev 없음
• Head 조정 필요

2. 삽입하려는 위치가 리스트 맨 끝일 때

• Tail 조정 필요

3. 빈 리스트에 삽일 할 때

• 이 두 조건에 의해 처리됨

 

# 연결리스트 연산 - 원소의 삽입
    def insertAt(self, pos, newNode):
        # pos의 위치가 유효한지 확인
        if pos < 1 or pos > self.nodeCount + 1 :
            # pos위치가 삽입할 수 있는 범위 밖에 있을 때 False 반환
            return False
        
        # 노드를 맨 처음 위치에 삽일할 때(prev없음)
        if pos == 1: # (빈 노드의 삽입할 조건에 걸림)
            newNode.next = self.head # 새로운 노드의 next는 head
            self.head = newNode # 헤드가 새로운노드가 된다
        
        # 삽입하려는 위치가 처음이 아닐 때
        else: 
            if pos == self.nodeCount + 1: # 삽입하려는 위치가 맨끝일 때
                prev = self.tail # prev == tail과 같음(앞에서 부터 찾을 필요 없음)
            else: # 삽입하려는 위치가 처음도 아니고 맨끝도 아닐 때
                prev = self.getAt(pos-1) # 끼워넣으려는 직전의 위치를 얻어낸다
            
            newNode.next = prev.next # 새로운 노드가 prev.next를 가르키도록한다.
            prev.next = newNode # prev.next를 newNode로 한다
        
        # 맨 마지막 위치에 삽입 할 때 (빈 노드의 삽입할 조건에 걸림)
        if pos == self.nodeCount + 1:
            self.tail = newNode # Tail을 새로운 노드로 변경
            
        # 마지막으로 노드의 갯수 증가
        self.nodeCount += 1
        return True

 

연결 리스트 원소 삽입의 복잡도

• 맨 앞에 삽입하는 경우 O(1)
• 중간에 삽입하는 경우 O(n)
• 맨 끝에 삽입하는 경우 O(1) -> tail을 가지고 있기 때문에

 

 

 

 

연결 리스트 연산 - 원소의 삭제

def pop(self, pos)

pos의 위치가 1<= pos <= nodeCount 안에 위치해야한다.

노드를 삭제하고 그 노드의 데이터를 리턴

pos를 curr에 담는다

prev.next에 curr.next를 담는다

curr의 데이터를 r에 저장하고 노드의 개수를 하나 줄여준다.

 

코드 구현 주의사항

1. 삭제하려는 node가 맨 앞의 것일 때

• prev가 없음
• Head 조정 필요

2. 리스트의 맨 끝의 node 를 삭제할 때

• Tail 조정 필요

3. 유일한 노드를 삭제할 때

• 이 두 조건에 의해 처리되는가?

 

 

삭제하려는 node가 마지막 node일 때, 즉 pos == nodeCount인 경우?

삽입하는 경우처럼 tail로 한 번에 처리할 수 없다. prev를 찾을 방법이 없으므로 앞에서부터 찾아와야한다.

 

    # 4. 연결리스트 연산 - 원소의 삭제
    def popAt(self, pos):
        # pop 값이 유효한지 확인 적당한 값이 아닐 경우 에러발생
        if pos < 1 or pos > self.nodeCount:
            raise IndexError
            
        # 맨 앞의 노드를 삭제하는 경우
        if pos == 1:
            curr = self.head
            self.head = self.getAt(pos+1)
            
            # 유일한 노드인 경우
            if self.nodeCount == 1:
                self.tail = None
                self.head = None
        
        # 맨 앞의 노드가 아닐 때
        else:
            prev = self.getAt(pos-1)
            curr = self.getAt(pos)
            prev.next = curr.next
            
            # 맨 끝 노드일 때
            if pos == self.nodeCount:
                self.tail = prev
                
        r = curr.data
        self.nodeCount -= 1
        
        return r

 

연결 리스트 원소 삭제의 복잡도

• 맨 앞에서 삭제하는 경우 O(1)
• 중간에서 삭제하는 경우 O(n)
• 맨 끝에서 삭제하는 경우 O(n)

 

 

 

 

연결 리스트 연산 - 두 리스트의 연결

def concat(self, L)

연결 리스트 self 의 뒤에 또 다른 연결 리스트인 L 을 이어붙임

    # 5. 연결 리스트 연산 - 두 리스트의 연결
    def concat(self, L):
        # 원래 리스트의 맨 끝이 이어붙이려는 리스트의 처음으로
        self.tail.next = L.head
        # 리스트 L이 비어있을 경우
        if L.tail:
            self.tail = L.tail
        self.nodeCount += L.nodeCount

 

 

 

 

 

연결 리스트가 힘을 발휘할 때

삽입과 삭제가 유연하다는 것이 가장 큰 장점

그런데 우리가 작성한 코드에서는 간단해 보이지 않는다. n번째에 있는 노드를 찾아야하기 때문에 처음부터 찾기가 부담이 될 수 있다 그래서 새로운 메서드를 만들게 되었다.

insertAfter(prev, newNode)

popAfter(prev)

어떤 노드를 주고 그 뒤에 있는 노드를 삽입 삭제할 수 있도록 정의를 한 메서드이다. 하지만 맨 앞에서 어떻게 해야할지 문제가 생기기 때문에 맨앞에 dummy node를 추가한 형태로 조금 변형된 연결 리스트를 만들었다.

더미 노드에 0번을 붙인다.

 

class LinkedList:
    # 더미노드 생성하는 생성자
    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = None
        self.head.next = self.tail

 

 

연산 정의

1. 길이 얻어내기
2. 리스트 순회
3. 특정 원소(k번째) 참조
4. 원소 삽입
5. 원소 삭제
6. 두 리스트 합치기

 

# 연결 리스트 연산 - 리스트 순회    

    def traverse(self):

        result = []

        curr = self.head

        # 기존과 다른 부분 curr.next가 존재하는 동안 반복

        while curr.next:

            curr = curr.next

            result.append(curr.data)

 

        return result