선형데이터구조, 연결리스트(LinkedList) #9 원형 연결리스트(Circular LinkedList)

1. 원형 연결 리스트(Circular Linked List)

• 원형 연결리스트는 기본적인 연결리스트에서 마지막 노드의 next 포인터가 리스트 맨 앞의 노드를 가리키는 리스트입니다.

• 일반적인 연결리스트는 head 포인터를 이용하여 리스트의 맨 앞에 노드를 추가하고, 맨 뒤의 노드의 next 포인터는 null을 가리킴
• 원형 연결리스트는 tail 포인터를 이용하여 리스트의 맨 뒤를 가리킬 수 있고, tail.next 포인터를 이용하여 리스트의 맨 앞의 노드를 가리킬 수 있음

 

2. 원형 연결 리스트의 추가, push

• 리스트의 tail 포인터를 이용하여 push 메서드 수행시 리스트의 맨 뒤에 노드를 추가합니다.

원형 연결 리스트의 push 수행 과정

1. newNode.next = tail.next
2. tail.next = newNode
3. tail = newNode

	/**
	 * 리스트 뒤에 데이터를 추가함
	 * @param data 추가하고자 하는 데이터 값
	 */
	@Override
	public void push(E data) {
		Node<E> newNode = new Node(data);
		
		if(tail == null)	// 리스트가 비어있는 경우
		{
			newNode.next = newNode;
		}
		else	// 리스트가 비어있지 않은 경우
		{
			// 맨 뒤 노드의 next는 맨 앞의 노드를 가리킴
			newNode.next = tail.next;
			// 기존 마지막 노드의 next는 newNode를 가리킴	
			tail.next = newNode;
		}
		
		// tail을 맨 뒤에 노드로 이동시킴
		tail = newNode;
		
		numofData++;
	}

	@Test
	void pushTest() {
		CircularList2<Integer> list = new CircularList2<Integer>();
		
		list.push(1);
		list.push(2);
		list.push(3);
		list.push(4);
		list.push(5);
		
		list.printList();
	}

1 2 3 4 5

 

3. 원형 연결 리스트의 제거, remove

• remote(E data) : 리스트의 노드들 중에서 data 값을 가진 노드를 제거합니다.

원형 연결 리스트의 remove 수행 과정

1. prev = tail
2. prev.next = cur.next

 

1. prev.next = cur.next
2. tail = prev

 

1. prev.next = cur.next

 

1. tail = null

 

	@Override
	public E remove(E data) {
		if(tail == null)
		{
			return null;
		}
		
		Node<E> cur = tail.next;
		Node<E> prev = new Node();

		// 삭제하고자 하는 노드를 탐색
		while(!cur.data.equals(data))
		{
			if(cur.next == tail.next)
			{
				break;	// not found
			}
			
			prev = cur;
			cur = cur.next;
		}
		
		// 노드가 단 한개인 경우
		if(cur == tail && cur.next == tail)
		{
			tail = null;
			numofData--;
			return (E) tail.data;
		}
		
		// 삭제하고자 하는 노드가 첫번째 노드인 경우
		if(cur == tail.next) 
		{
			prev = tail;
			
			prev.next = cur.next;
		}
		else if(cur == tail)	// 삭제 노드가 마지막 노드인 경우 
		{
			prev.next = tail.next;
			tail = prev;
		}
		else
		{
			prev.next = cur.next;
		}

		numofData--;
		return (E) cur.data;
	}

	@Test
	void removeTest() {
		CircularList2<Integer> list = new CircularList2<Integer>();
		
		// 12 -> 56 -> 2 -> 11
		list.push(12);
		list.push(56);
		list.push(2);
		list.push(11);
	
		// 12 -> 56 -> 2 -> 11, before
		// 56 -> 2 -> 11 after
		list.remove(12);	// 제일 앞의 노드 제거
		list.printList();

		// 56 -> 2 -> 11, before
		// 56 -> 2, after
		list.remove(11);	// 제일 뒤 노드 제거
		list.printList();
		
		// 56 -> 2 -> 10, before
		// 56 -> 10, after
		list.push(10);
		list.remove(2);		// 중간 노드 제거
		list.printList();
	}

56 2 11 
56 2 
56 10

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/LinkedList/Implement/circularList
https://www.geeksforgeeks.org/circular-linked-list/