Data Structure - Linked List(1)

Data Structure - Linked List

Linked List

Linked List는 연결리스트라고 한다.
배열은 데이터가 특정 공간에 순차적으로 나열되어 있다면,
Linked List는 나열 되어 있는 것이 아닌 다음 데이터를 가르키는 포인터가 있다.

링크드리스트에는 다양한 종류가 있다. 그중 single linked list와
double linked list에 대해서 알아보자.

Single Linked List는 다음 노드를 가르키는 포인터가 있다면,
Double Linked List는 이전과 다음 노드를 가르키는 포인터가 있다.

링크드 리스트의 기본 용어

• Node
  데이터를 저장하는 단위(데이터, Pointer)

• Pointer
  다음 데이터를 가르키는 것으로, 연결정보를 가지고 있다.
  
  

링크드 리스트의 장점은 배열 처럼 미리 데이터 저장을 위한 공간을 만들 필요가 없다는 것이다. 데이터가 추가 될때 마다, 저장할 공간이 생기는 것과 같다.

단점으로는 포인터가 필요하다라는 점과, 데이터를 찾는데 접근 속도가 느리다는점과, 중간데이터의 추가, 삭제를 위한 부가적인 작업이 필요하다느 점이다.

Single Linked List

Node구현

class Node:
	def __init__(self, data):
    	self.data = data
        self.next = None #제일 첫번째 노드는 next가 None이다.

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

Linked List 구현 (addNode,desc메서드)

addNode()는 노드가 추가 될때 호출하는 메서드이다.
desc()는 노드의 정보를 추력하는 메서드이다.

addNode()의 경우 추가되는 노드는 노드의 맨 마지막 위치로 이동해야 하며,
현재 마지막노드가, 추가되는 노드를 가르키도록 해야 한다.

desc()는 노드를 하나씩 순회하면서 노드의 정보를 출력하는 것이다.

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


class Linkedlist:

    def __init__(self):
        self.head = None

    def addNode(self, data):
        if self.head == None:
            self.head = Node(data)

        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)

    def desc(self):
        if self.head == None:
            print("데이터가 없습니다.")
        else:
            node = self.head
            while node:
                print(node.data)
                node = node.next


node = Linkedlist(0)
for i in range(1,10):
    node.addNode(i)

# node.desc()

print(node.head.data, end=" 다음은 =>")
print(node.head.next.data ,end=" 다음은 =>")
print(node.head.next.next.data,end=" 다음은 =>")
print(node.head.next.next.next.data,end=" 다음은 =>")
print(node.head.next.next.next.next.data,end=" 다음은 =>")
print(node.head.next.next.next.next.next.data,end=" 다음은 =>")
print(node.head.next.next.next.next.next.next.data,end=" 다음은 =>")
print(node.head.next.next.next.next.next.next.next.data,end=" 다음은 =>")
print(node.head.next.next.next.next.next.next.next.next.data,end=" 다음은 =>")
print(node.head.next.next.next.next.next.next.next.next.next.data)

#0 다음은 =>1 다음은 =>2 다음은 =>3 다음은 =>4 다음은 =>5 다음은 =>6 다음은 =>7 다음은 =>8 다음은 =>9

Linked List 구현 (delNode메서드)

del노드는 특정노드를 삭제하는 것이다.
특정노드를 삭제하기 위해서는 노드의 위치를 알아야 한다.
그리고 삭제되는 노드의 앞에 노드와 삭제되는 노드의 뒤의 노드를 연결 해주어야 한다.

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



class Linkedlist:

    def __init__(self,data):
        self.head = Node(data)



    def addNode(self, data):
        if self.head == None:
            self.head = Node(data)

        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)



    def desc(self):
        if self.head == None:
            print("데이터가 없습니다.")
        else:
            node = self.head
            while node:
                print(node.data)
                node = node.next




    def delNode(self, isdata):
        
        #case1 : 노드가 하나도 없는 경우 삭제할려고 해도 삭제할 노드가 없다.
        if self.head == None: 
            print("삭제할 노드가 없습니다.")
		
        #case2 : head가 삭제할 노드인 경우
        if self.head.data == isdata:
            temp = self.head
            self.head = self.head.next
            del temp
		
        #case3 : 그외의 경우
        else:
            node = self.head
            # while node: # 이렇게 하면 노드의 이전 정보를 알수 없다.
            #     if node.data == isdata:
            # 삭제할 노드를 찾는다고 해도 앞과 뒤를 연결할 정보가 없다.
            # 그리고 node.next != None을 해도 마지막까지 보게 된다.
            # node.next이므로 1,2,3~~,8,9 인 경우 8에서 8의 다음요소인 9를 판단한다.
            
            while node.next :
                if node.next.data == isdata:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    pass
                else:
                    node = node.next    
            


            
node = Linkedlist(0)
for i in range(1,10):
    node.addNode(i)

node.desc()
print("==========")
node.delNode(3)
node.desc()

Linked List 구현 (addInsideNode메서드)

addInsideNode를 호출시 추가할 데이터와, 추가할 데이터의 앞에 데이터를 인자로 준다.
추가할 데이터의 위치를 찾아서 데이터를 추가해주고 다음위치를 조정해준다.

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



class Linkedlist:

    def __init__(self,data):
        self.head = Node(data)


    def addNode(self, data):
        if self.head == None:
            self.head = Node(data)

        else:
            node = self.head
            while node.next:
                node = node.next
            node.next = Node(data)


    def desc(self):
        if self.head == None:
            print("데이터가 없습니다.")
        else:
            node = self.head
            while node:
                print(node.data)
                node = node.next


    def delNode(self, isdata):
        
        if self.head == None:
            print("삭제할 노드가 없습니다.")

        if self.head.data == isdata:
            temp = self.head
            self.head = self.head.next
            del temp

        else:
            node = self.head
            # while node: # 이렇게 하면 노드의 이전 정보를 알수 없다.
            #     if node.data == isdata:
            while node.next :
                if node.next.data == isdata:
                    temp = node.next
                    node.next = node.next.next
                    del temp
                    pass
                else:
                    node = node.next    

# 방법1    
# 순회하면서 데이터를 비교
# 바로 추가

    def addInsideData(self, addData, existData):
        node = self.head
        if self.head == None:
            self.head = Node(addData)        
        
        else: 
            if node.data ==  existData:
                temp = node.next
                node.next = Node(addData)
                node.next.next = temp
            else:
                while node.next:
                    if node.next.data == existData:
                        temp = node.next.next
                        node.next = Node(addData)
                        node.next.next = temp
                    else:
                        node = node.next 
                print(node.data)
                
                node.next = Node(addData)


# 방법2 
# search()함수를 정의해서 풀이

    def search(self,isData):
        node = self.head
        if self.head == None:
            return None
        else:
            while node:
                if node.data == isData:
                    return node
                else:
                    node = node.next                     
            return None

    def addInsideNode_search(self,addData, isData):
        searched = self.search(isData)

        if searched == None:
            self.addNode(addData)
        else:
            addNodenext = searched.next
            searched.next = Node(addData)
            searched.next.next = addNodenext 
            

참고

https://www.fun-coding.org/daveblog.html