[자료구조 공부기록] 2. List(Linked List) + Python 구현

Linked List 예시

일반적인 특징

• 선형구조의 자료구조 입니다.
• 배열과 달리 순서가 중요하기 때문에 sequence(시퀀스)라고도 부릅니다.
• 구현 방식이 두 가지로 나뉩니다.
  • Array List : 배열과 비슷한 방식으로 구현됩니다.
  • Linked List : 처음 그림과 같이 다음 노드의 주소를 가지고 찾아가는 방식입니다.
• 사이즈 크기가 변하는 동적 자료형입니다. 

 

장점 및 단점 

 

1) 장점

• 배열과 비교하면 삽입과 삭제가 편합니다. 

Linked List의 삭제 예시

삭제를 한다고 하면 Array(배열)과 달리 원소들을 당기거나 밀어낼 필요 없이 다음 노드의 주소만 바꿔주면 됩니다. 

 

삽입도 마찬가지로 노드의 주소만 바꿔 주면 되므로 배열에 비해 삽입과 삭제가 간단해진 것입니다. 

 

 

2) 단점

• (상대적으로) 배열에 비하면 검색이 느립니다.
• 주소를 담고 있는 포인터에 메모리가 낭비됩니다.

 

리스트 자료형은 명확한 단점이라고 할 만한 게 없는 듯합니다. 언어마다 구현 방식이 많이 다르고

 

각자 효율적인 부분이 다르기 때문에 여러 언어를 쓴다면 이런 점이 오히려 단점이라면 단점이라고 볼 수 있을 듯합니다.

---

출처 : https://www.faceprep.in/data-structures/linked-list-introduction/

 

사실 Linked List에는 일반적인 종류가 3가지 있습니다. 

 

1. 앞에서 계속 설명한 형태의 Singliy Linked List
2. 앞 뒤의 노드의 주소를 가지고 있는 Doubly Linked List
3. 마지막 노드의 주소가 제일 첫 노드를 가리키는 Circular Linked List

위의 이미지를 보시면 큰 차이는 없으나 각 주소를 가리키는 포인터가 어떤 형식으로 구성되어 있나 확인하신다면

 

큰 어려움 없이 이해가 가실 거라 생각합니다.

 

아래쪽에 Singliy Linked List를 구현해봤습니다. 

 

---

---

 

# Node 클래스 정의
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
        
# Single Linked List 클래스 정의
class Single_linked_list:
    # class 생성시 head, tail node 생성 및 연결
    # next에서 현재 노드 위치를 표시할 cur
    # 길이를 반환해줄 len
    def __init__(self):

        Head = Node(None)

        self.head = Head
        self.tail = Head
        self.head.next = self.tail

        self.cur = self.head
        
        self.len = 0

    # 데이터 추가 함수
    def append(self, data, idx=None):

        insert_node = Node(data)
        
        # idx가 없거나 리스트 길이와 같을 경우
        # 바로 tail 노드를 사용하여 추가
        if idx == None or self.len == idx:
            self.tail.next = insert_node
            self.tail = insert_node
            
            # 길이 추가
            self.len += 1
            
        # 중간 삽입의 경우
        # 앞에서부터 돌아가며 해당 노드에 도착해야함
        elif self.len > idx:
            
            # 노드를 head에서부터 시작
            self.Node = self.head
            
            # 노드 순차검색
            for x in range(idx):
                self.Node = self.Node.next
            
            # 목적 노드에 도달한 경우 노드 삽입
            self.temp = insert_node
            self.temp.next = self.Node.next
            self.Node.next = self.temp
            
            # 길이 추가
            self.len += 1
            
        else:
            # 인덱스 길이가 너무 길 경우 에러 발생
            print(f'list의 길이: {self.len}, 요청된 인덱스:{idx}')
        

    # 데이터 삭제 함수
    def delete(self, data=None, idx=None):

        # len 감소 여부
        decrease_flag = False
        
        # 마찬가지로 head에서 시작
        self.Node = self.head
        
        # head에서 순차적으로 검색
        for Node_num in range(self.len):
            # data는 주어지고 idx는 주어지지 않은 경우
            
            if data != None and idx == None:
                # data가 있을 경우 삭제
                # cur이 해당 노드 일 경우 앞의 노드로 가져옴
                if self.Node.next.data == data:
                    if self.cur == self.Node.next:
                        self.Node.next = self.Node.next.next
                        self.cur = self.Node
                    else:
                        self.Node.next = self.Node.next.next
                        
                    decrease_flag = True
                    break
            
            # idx가 주어지고 data는 주어지지 않은 경우
            elif idx != None and data == None:
                
                # idx가 0일때
                if idx == 0 and self.cur == self.head:
                    self.Node = self.head.next
                    self.head = self.Node
                    self.cur = self.head
                    break
                elif idx == 0 and self.cur != self.head:
                    self.Node = self.head.next
                    self.head = self.Node
                    break
                    
                # idx가 너무 큰 경우
                if idx >= self.len:                    
                    print(f'idx 크기가 너무 큽니다. 리스트 길이:{self.len}, idx:{idx}')
                    decrease_flag = False
                    break
                                    
                # 전 노드에서 멈춤
                if (idx -1) == Node_num:
                
                # data가 있을 경우 삭제
                    if self.cur == self.Node.next:
                        # 다음 노드를 가리키는 주소를 다다음 노드로 연결
                        self.Node.next = self.Node.next.next
                        self.cur = self.Node
                    else:
                        self.Node.next = self.Node.next.next
                    
                    decrease_flag = True
                    break
                    
            # data와 idx 모두 주어진 경우
            else:
                # idx가 너무 큰 경우
                if idx > self.len:
                    print(f'idx 크기가 너무 큽니다. 리스트 길이:{self.len}, idx:{idx}')
                    decrease_flag = False
                    break
                    
                # idx가 0일때
                if idx == 0 and self.cur == self.head:
                    temp_Node = self.head.next
                    self.head = temp_Node
                    self.cur = self.head
                    break
                elif idx == 0 and self.cur != self.head:
                    temp_Node = self.head.next
                    self.head = temp_Node
                    break
                
                # 삭제할 이전의 노드에서 작업
                if (idx -1) == Node_num:
                    
                    # 데이터가 동일할 경우 삭제 
                    if self.Node.next.data == data:
                        # cur이 해당 노드 일 경우 앞의 노드로 가져옴
                        if self.cur == self.Node.next:
                            self.Node.next = self.Node.next.next
                            self.cur = self.Node
                        else:
                            self.Node.next = self.Node.next.next
                            break
                        
                        decrease_flag = True
                    else:
                        print(f'{idx}번 노드 데이터 : {self.Node.next.data}')
                        decrease_flag = False
                    
                    break
            
            # 노드 이동
            self.Node = self.Node.next
        
        # len 감소
        if decrease_flag:
            self.len -= 1
            
    
    # 앞에서 부터 데이터 return
    def next(self):
        # 다음 노드가 비어있을 경우 안내메시지
        if self.cur.next == None:
            print('이미 마지막 노드입니다.')
        else:
            # head 부터 시작하기 때문에 cur next로 이동
            self.cur = self.cur.next
            
        return self.cur.data
    
    # len 호출시 self.len return
    def __len__(self):
        return self.len
    
    
    # 모든 원소를 보기 위한 임시 함수
    def print_all(self):
        
        self.Node = self.head
        return_str = "|"
        for Node_num in range(self.len-1):
            self.Node = self.Node.next
            return_str = return_str + str(self.Node.data) + '|'
            

        return return_str
    



# List 선언
a = Single_linked_list()

# 데이터 삽입
a.append(1)
a.append(2)
a.append(4)
a.append(3, 2)
a.append(5)
a.append(7)
a.append(8)
a.append(6, 5)
a.append(9, 8)
a.append(0, 0)

# 데이터 확인
print(a.print_all())


# 데이터 삭제시마다 데이터 확인
a.delete(5, 0)
print(a.print_all())
a.delete(5)
print(a.print_all())
a.delete(idx = 1)
print(a.print_all())
a.delete(0,0)
print(a.print_all())

 

잘 짜인 코드는 아닙니다만 짜보는 것 자체가 의미 있는 듯합니다.

 

print_all이라는 메서드를 생성하여 확인하기 쉽게 만들었습니다.