[Python] 단순 연결리스트 구현

단순 연결리스트는 한 방향으로만 링크를 갖는 구조이다

구현하려는 단순 연결리스트의 추상 데이터 타입은 다음과 같다

• isempty() : 비었다면 True를, 아닐 경우 False를 반환
• add_first(item) : 연결리스트의 첫 번째 자리에 item을 삽입
• add_last(item) : 연결리스트의 마지막에 item을 삽입
• insert(pos, item) : pos 위치에 item을 삽입 (첫 번째 자리는 0부터 시작한다)
• remove(target) : target이 존재할 경우 target을 제거
• search_target(target) : target이 존재할 경우 pos를 반환, 없을 경우 False를 반환
• search_pos(pos) : pos위치에 존재하는 값을 반환, 없을 경우 False를 반환
• size() : 연결리스트의 크기를 반환
• print() : 연결리스트를 순환하면서 값을 출력

---

1. 노드

연결리스트를 나타내기에 앞서 연결리스트를 이루는 노드를 나타내자

class Node(object):
    def __init__(self, value=None, pointer=None):
        self.value = value
        self.pointer = pointer

노드는 값을 저장하는 Value와 다음 노드를 가리키는 pointer를 멤버로 갖는다

 

2. 연결리스트

class Linked_List(object):
    def __init__(self):
        self.head = None
        self.length = 0

연결리스트의 시작 노드를 가리키는 head와 연결리스트의 길이를 저장하는 length를 갖는다

head는 연결리스트의 첫 번째 원소를 나타낸다

 

1) isempty()

def isempty(self):
    return not bool(self.head)

head가 존재하는 경우 False를, 존재하지 않는 경우 True를 반환한다

 

2) add_first(item)

리스트가 비어있지 않은 경우	1. 새로운 노드가 기존 head노드(첫노드)를 가리키게 한다  2. head가 새로운 노드를 가리키게 한다
리스트가 비어있는 경우	head가 새로운 노드를 가리키게 한다
연결리스트의 길이를 1만큼 증가시킨다

def add_first(self, item):
    node = Node(item)
    if not self.isempty():
        node.pointer = self.head
        self.head = node
    else:
        self.head = node
    self.length += 1

3) add_last(item)

리스트가 비어있지 않은 경우	1. node가 self.head를 가리키게 한다 (iterator 용도) 2. node의 pointer가 None을 가리킬 때까지 순환한다 3. 마지막 노드의 pointer가 새로운 노드를 가리키게 한다
리스트가 비어있는 경우	head가 새로운 노드를 가리키게 한다
연결리스트의 길이를 1만큼 증가시킨다

def add_last(self, item):
    if not self.isempty():
        node = self.head
        while node.pointer:
            node = node.pointer
        node.pointer = (Node(item))
    else:
        self.head = Node(item)
    self.length += 1

4) insert(pos, item)

처음 시작 위치는 0이다(pos=0 은 맨 앞에 삽입)

pos가 0인 경우	add_first() 호출
pos가 length(마지막)인 경우	add_last() 호출
0<pos<length인 경우	1. pos 위치에 삽입하기 이전의 노드를 알고 있어야 한다 2. 삽입하기 이전의 노드 값을 찾을 때까지순환한다 3. 새로 삽입할 노드는 삽입 이전 노드가 가리키는 노드를 가리키도록 한다 4. 삽입 이전 노드가 새로 삽입된 노드를 가리키도록 한다
연결리스트의 길이를 1만큼 증가시킨다

def insert(self, pos, item):
    if not self.isempty():
        if pos == 0:
            self.add_first(item)

        elif pos == self.length:
            self.add_last(item)

        else:
            node = self.head
            cnt = 0
            while pos > 0 and pos < self.length:
                if cnt == pos - 1:
                    new_node = Node(item, node.pointer)
                    node.pointer = new_node
                    break
                node = node.pointer
                cnt += 1
            self.length += 1
    else:
        print('list is empty')

5) remove(target)

target을 입력받아 연결리스트 안에 target이 있을 경우 target을 지운다

첫번째 노드의 값이 target인 경우	head가 노드의 pointer(다음 원소)를 가리키게 한다
그 외의 경우	1. node.value == target을 만족할 때까지 prev와 node를 순환한다 2. prev에 삭제 이전 노드를 저장, node에 삭제할 노드를 저장한다 3. node.value == target일 때, prev의 pointer는 node의 pointer를 가리킨다 4. node값을 없애고 True를 반환한다 5. 값이 없을 경우 False를 반환한다
연결리스트의 길이를 1만큼 감소시킨다

def remove(self, target):
    if not self.isempty():
        node = self.head
        if node.value == target:
            self.head = node.pointer
            self.length -= 1
            return True
        else:
            prev = node
            node = node.pointer
            while node:
                if node.value == target:
                    prev.pointer = node.pointer
                    node = None
                    self.length -= 1
                    return True
                prev = node
                node = node.pointer
            return False
    else:
        print('list is empty')
        return False

6) search_target(target)

target을 입력받아 연결리스트에서 target의 pos를 반환한다

def search_target(self, target):
    if not self.isempty():
        pos = 0
        node = self.head
        while node:
            if node.value == target:
                return pos
            node = node.pointer
            pos += 1
        return False
    else:
        print('list is empty')
        return False

target이 연결리스트 안에 존재하면 pos를, 없으면 False를 반환한다

 

7) search_pos(pos)

pos를 입력받아 연결리스트에서 pos에 해당하는 값을 반환한다

첫 번째 원소의 pos는 0이라 한다

def search_pos(self, pos):
    if not self.isempty():
        cnt = 0
        node = self.head
        while node:
            if cnt == pos:
                return node.value
            node = node.pointer
            cnt += 1
        return False
    else:
        print('list is empty')
        return False

cnt값을 증가시켜 가며 pos에 해당하는 값을 반환한다

pos가 연결리스트의 크기를 벗어나거나 연결리스트가 없으면 False를 반환한다

 

8) size()

def size(self):
    return self.length

연결리스트의 크기를 반환한다

 

9) print()

def print(self):
    if not self.isempty():
        node = self.head
        while node:
            print(node.value, end=' ')
            node = node.pointer
        print()
    else:
        print('list is empty')

1. node가 연결리스트의 head(첫 번째 원소)를 가리키게 한다

2. 연결리스트를 순환하면서 값을 출력하도록 한다

 

3. 예제 코드

if __name__ == '__main__':
    list = Linked_List()
    print(list.isempty())
    list.add_last(5);    print('size is ', list.size()); list.print()
    list.add_last(9);    print('size is ', list.size()); list.print()
    list.add_first(3);    print('size is ', list.size()); list.print()
    list.insert(2, 7);    print('size is ', list.size()); list.print()
    list.insert(0, 8);    print('size is ', list.size()); list.print()
    list.remove(8);    print('size is ', list.size()); list.print()

#출력값
True
size is  1
5
size is  2
5 9
size is  3
3 5 9
size is  4
3 5 7 9
size is  5
8 3 5 7 9
size is  5
3 5 7 9

 

4. 전체코드

class Node(object):
    def __init__(self, value=None, pointer=None):
        self.value = value
        self.pointer = pointer

class Linked_List(object):
    def __init__(self):
        self.head = None
        self.length = 0

    def isempty(self):
        return not bool(self.head)

    def add_first(self, item):
        node = Node(item)
        if not self.isempty():
            node.pointer = self.head
            self.head = node
        else:
            self.head = node
        self.length += 1

    def add_last(self, item):
        if not self.isempty():
            node = self.head
            while node.pointer:
                node = node.pointer
            node.pointer = (Node(item))
        else:
            self.head = Node(item)
        self.length += 1

    def insert(self, pos, item):
        if not self.isempty():
            if pos == 0:
                self.add_first(item)

            elif pos == self.length:
                self.add_last(item)

            else:
                node = self.head
                cnt = 0
                while pos > 0 and pos < self.length:
                    if cnt == pos - 1:
                        new_node = Node(item, node.pointer)
                        node.pointer = new_node
                        break
                    node = node.pointer
                    cnt += 1
                self.length += 1
        else:
            print('list is empty')

    def remove(self, target):
        if not self.isempty():
            node = self.head
            if node.value == target:
                self.head = node.pointer
                self.length -=1
                return True
            else:
                prev = node
                node = node.pointer
                while node:
                    if node.value == target:
                        prev.pointer = node.pointer
                        node = None
                        self.length -= 1
                        return True
                    prev = node
                    node = node.pointer
                return False
        else:
            print('list is empty')
            return False

    def search_target(self, target):
        if not self.isempty():
            pos = 0
            node = self.head
            while node:
                if node.value == target:
                    return pos
                node = node.pointer
                pos += 1
            return False
        else:
            print('list is empty')
            return False

    def search_pos(self, pos):
        if not self.isempty():
            cnt = 0
            node = self.head
            while node:
                if cnt == pos:
                    return node.value
                node = node.pointer
                cnt += 1
            return False
        else:
            print('list is empty')
            return False

    def size(self):
        return self.length

    def print(self):
        if not self.isempty():
            node = self.head
            while node:
                print(node.value, end=' ')
                node = node.pointer
            print()
        else:
            print('list is empty')

if __name__ == '__main__':
    list = Linked_List()
    print(list.isempty())
    list.add_last(5);    print('size is ', list.size()); list.print()
    list.add_last(9);    print('size is ', list.size()); list.print()
    list.add_first(3);    print('size is ', list.size()); list.print()
    list.insert(2, 7);    print('size is ', list.size()); list.print()
    list.insert(0, 8);    print('size is ', list.size()); list.print()
    list.remove(8);    print('size is ', list.size()); list.print()