[자료구조] linked list

*sort 함수 변형 유의하기

*node=self.head 형태 delete 함수에서 유의하기

 

sll singly linked list

cll circular linked list

dll doubly linked list

 

Node에는 data, link 값 초기화

SLL 함수에는 head, node 값 초기화 

self. head가 존재한다는 것은 비어있지 않다는 의미 

 

 

 

1.attach 

뒤에다 붙이는 거니까 self.tail이 있는지 검사해서 뒤에다 붙이는 과정

 

2. insert

prev 값을 기존에 받기 때문에 prev 값이 존재하는지의 여부를 따져서 

if prev is none : 제일 앞에 추가 node.link=self. head self.head=node

prev 존재한다면 find 함수 이용하기(temp 변수)

node.link=temp.link temp.link=node

제일 뒤에 있으면 if not node.link: self.tail=node

 

3. sort

head의 이름을 temp로 생각

prev 값을 none 으로 설정해두고 

item과 temp.data 비교하기 #가장 앞에 있는 값부터 순차적으로 비교하는 과정

1. temp.data가 더 작으면 이 값을 temp를 prev로 설정해서 temp 값을 뒤의 값으로 옮긴다 #temp값과 비교하는 과정 계속하기 위해서

2. temp.data가 더 크면 node.link와 temp 연결하기

1) prev 값이 있으면  prev.link=node

2) prev 값이 없으면 self.head=node

 

다 거쳐도 더 큰 값 찾지 못하면 그 값이 최대인 것!

prev.link=node

self.tail.node

 

4.delete

find함수로 prev,node 찾기

1. node값이 없으면 오류

2. prev 값이 있으면 중간노드 prev.link=node.link 

3. prev 값이 없으면 제일 앞의 값 self.head=node인 경우에는 self.head=node.link로 수정하기

4. 가장 끝의 값이라면 node=self.tail이라면 self.tail=prev 로 바꾸기 

 

5.find

temp.data=item이 될 때까지 temp 값을 계속 하나씩 뒤로 보내기

prev=temp temp=temp.link

-> 같아지면 prev랑 temp값 출력하기

return prev,  temp 

 

6.view

temp값을 하나씩 뒤로 보내면서 temp.data 출력하기(while temp일 동안)

self.head 가 있는 동안에는 처음값, 끝값 출력하기 self.head 가 없는 경우에는 empty하다는 사실 알리기

 

7.length count변수 이용

temp 값을 하나씩 뒤로 보내면서 count하기

while temp:

count+=1

temp=temp.link

temp=none이 되면 더 이상 count 변수 증가하지 않음

 

8.del list()

node=self.head로 설정(self.head 이 node 값을 가리키도록 한다) 

temp=node

node=node.link

del temp -> 이후 temp 값 계속 재정의하기

 

node가 none 이 되면 끝. self.head=None로 바꿔주기(empty라는 뜻)   

 

9.concat (리스트 연결하기)

1. first 가 비어있으면 -> return second

2. 아니면 temp=temp.link 로 계속 뒤로 보내기 이후에 temp.link=second 해주기 -> self.head 반환

O(length of first list)

 

*linked stack 은 linked list의 연결 방향과 방향이 반대임

즉 head 값이 stack 이 되는 것

*peek front=> 지우지 않고 반환만 하는 역할 return self. head.data

 

linked stack

1)add.front

node.link=self.head

self.head=node

 

2)pop front

temp=self.head

self.head=self.head.link

del temp

 

linked queue

3)add rear

if not self.head  #empty인 경우를 먼저 추가하고

elif self.tail  #tail 이 없는 경우에 추가한다

node

self.tail.link=node

self.tail=node

 

4)pop rear

현재 값을 item에 넣고 find 함수 이용해 prev 반환

find 함수 사용하기(이전 값을 알아야하니까)

self.tail=prev

prev 값이 존재하면

prev.link=none

존재하지 않는다면 가장 앞이니까

self.head=none

 

*값을 제거하기 전에 tail 값을 prev로 옮겨 놓아야 tail 값이 남아있게 됨

 

circular list

circular list length O(list length)

temp=self.head로 설정해 놓고

temp=temp.link 로 계속 돌리기

다시 temp=self.head가 되면 멈추면 됨

 

circular list에서 중간에 추가할 때

node.link=self.head

add.sort 함수에서 변형하기

 

reverse 

self.tail=self.head

while first:

third=second

second=first

first=first.link(하나씩 뒤로 밀기)

second.link=third

다 끝나면 self.head=second

O(list length)

 

doubly linked list 이중연결리스트(prev 필요없음)

-> 이진트리 활용

head node가 있는 상황만 생각하기

self.head.rlink=self.head

 

add

node.llink=self.head.llink

node.rlink=self.head

self.head.llink.rlink=node

self.head.llink=node

 

del

node.llink.rlink=node.rlink

node.rlink.llink=node.llink

->node의 rlink가 가리키는 값의 llink가 가리키는 값