링크드리스트

연결리스트

 

1. 링크드리스트  구조

• 링크드리스트는 떨어진 곳을 존재하느 데이터를 포인터로 가르켜서 관리하는 구조
• C언어에서는 포인터를 사용하여 다음 주소를 가르키도록 하지만, python에서는 객제지향을 가지고 구현
• 링크드리스트의 기본 용어
  노드(Node) : 데이터의 기본 저장 단위(데이터값, 포인터)로 구성
  포인터(Pointer) : 각 노드안에서 다음 Node와의 연결정보를 가지고 있음

링크드리스트

2. Python으로 구현한 링크드 리스트 

class Node:
	def __init__(self, data, next=None):
        self.data = data
        delf.next = next
 
 node1 = Node(1)
 node2 = Node(2)
 
 node1.next = node2


tNode = node1
while tNode.next:
	print(tNode.data)
 

visualgo.net/en/list

VisuAlgo - Linked List (Single, Doubly), Stack, Queue, Deque

3. 장점 / 단점 

- 장점 

미리 데이터 공간을 할당할 필요가 없다.

배열은 미리 데이터 공간을 할당 해야한다.

 

- 단점

다음 노드를 위한 별도의 공간이 필요하다. 

배열은 인덱스로 바로 접근 가능한 반면 링크드리스트는 맨 앞에서부터 접근 해야한다. 

접근 속도가 느리다. 

중간 데이터 삽입,삭제시에 데이터 연결을 재설정해야된다.

 

파이썬 객체지향 프로그래밍으로 링크드리스트 구현하기

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

class NodeManager:
  def __init__(self, data):
    self.head = Node(data)
  
  #출력
  def desc(self):
    if self.head == None:
      print("no head")
      return
    node = self.head
    while node:
      print(node.data)
      node = node.next
  #추가
  def add(self, data):
    if self.head == '':
      self.head = Node(data)
    else:
      node = self.head
      while node.next:
        node = node.next
      node.next = Node(data)
  #삭제
  def delete(self, data):
    #헤드일경우
    if self.head == '':
      print("no head")
      return
    if self.head.data == data:
      temp = self.head
      self.head = self.head.next
      del temp
      print('delete head')
      return
    else: #헤드가 아닐 경우
      print('delete not head')
      node = self.head
      while node.next:
        if node.next.data == data:
          temp = node.next
          node.next = node.next.next
          del temp
          return
        else:
          node = node.next
  #찾기 함수
  def find(self, data):
    if self.head == None:
      print("not node")
      return
    if self.head == '':
      print("not head")
      return

    node = self.head
    while node.next:
      if node.data == data:
        print("find data")
        return
      else:
        node = node.next


linked = NodeManager(1)


for data in range(2, 10):
  linked.add(data)
linked.desc()

linked.find(10)

 

이중 링크드리스트

 

 

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

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

# 하나만 넣어볼 경우
  def insert(self, data):
    if self.head == None:
      self.head = Node(data)
    else:
      node = self.head
      while node.next:
        node = node.next
      new = Node(data)
      node.next = new
      new.prev = node
      self.tail = new
#특정 위치앞에 삽입
  def insert_from_before(self, data, before):
    if self.head == None:
      self.head = Node(data)
      self.tail = self.head
      return True
    else:
      node = self.tail
      while node.data != before:
        node = node.prev
        if node == None:
          return False
      # 하나 앞의 노드를 기억해두고
      before_node = node.prev
      # 새로운 노드를 만들때 위치를 지정해준다
      new = Node(data, before_node, node)

      if before_node: #전의 노드의 위치를 new로 바꿔준다.
        before_node.prev = new
      else:
        self.head = new
      node.prev = new
      return True
#특정 위치 뒤에 삽입
  def insert_from_after(self, data, after):
    if self.head == None:
      self.head = Node(data)
      self.tail = self.head
      return True
    else:
      node = self.head

      while node.data != after:
        node = node.next
        if node == None:
          return False
      
      next_node = node.next
      new = Node(data, node, next_node)

      if new:
        next_node.prev = new
      else:
        self.tail = new
    def desc(self):
      node = self.head
      while node:
          print(node.data)
          node = node.next