DevAlgorithm

[Data Structure] Linked-list

  1. 1. 단순 Linked list (Singly Linked List)
  2. 2. 원형 Linked list (Circular Linked List)
  3. 3. 이중 Linked list (Doubly Linked List)
  4. 4. 참조

Linked List는 각 Data들을 Pointer로 연결하여 관리하는 구조이다.

첫 번째 Node인 Head pointer가 다음 Node를 가리키고 그 Node는 다음 Node를 가리킨다.

맨 마지막 Node에는 더 이상 다음 Node를 가리키는 Pointer가 없는데 이를 Tail Node라 한다.

단순 Linked list (Singly Linked List)

  • 단순히 Head부터 Tail까지 이어져 있는 구조.

우선 Node를 아래와 같이 구성하고.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Node {
	Node mNext;
	Node mPrev;
	
	int mData;
	
	Node(int data) {
		mData = data;
	}
	
	public void setPrevious(Node prev) {
		mPrev = prev;
	}
	
	public void setNext(Node next) {
		mNext = next;
	}
	
	public void setData(int data) {
		mData = data;
	}
	
	public Node getPrev() {
		return mPrev;
	}
	
	public Node getNext() {
		return mNext;
	}
	
	public int getData() {
		return mData;
	}
}

단일 Linked List는 아래와 같이 구성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
public class SinglyLinkedList {
	Node mHead;
	Node mTail;
	
	SinglyLinkedList(Node newNode) {
		mHead = newNode;
		mTail = newNode;
	}
	
	public void addNode(Node newNode) {
		mTail.setNext(newNode);
		mTail = newNode;
	}
		
	public void insertNode(Node newNode, int offset) {
		Node temp = mHead;
		
		for (int i = 1; i < offset; i++) {
			temp = temp.getNext();
		}
		
		newNode.setNext(temp.getNext());
		temp.setNext(newNode);
	}
	
	public void deleteNode(int offset) {
		Node temp = mHead;
		Node delNode;
		
		for (int i = 1; i < offset - 1; i++) {
			temp = temp.getNext();
		}
		
		delNode = temp.getNext();
		temp.setNext(delNode.getNext());
		delNode = null;
	}
	
	public void printNodes() {
		Node temp = mHead;;
		
		while (temp != null) {
			System.out.print(temp.getData() + " ");
			temp = temp.getNext();
		}
		System.out.println();
	}
}

Main에서 아래와 같이 확인해보면

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Main {
	public static void main(String[] args) {
		SinglyLinkedList sll = new SinglyLinkedList(new Node(1));
		
		sll.addNode(new Node(2));
		sll.addNode(new Node(3));
		sll.addNode(new Node(4));
		sll.addNode(new Node(5));
		sll.printNodes();
		
		sll.insertNode(new Node(8), 3);
		sll.printNodes();
		
		sll.deleteNode(2);
		sll.printNodes();
	}
}

아래와 같은 결과를 얻을 수 있다.

1 2 3 4 5 
1 2 3 8 4 5 
1 3 8 4 5

원형 Linked list (Circular Linked List)

  • Tail이 Head를 가리키는 원형 구조.

Node는 위에 구성했던 것을 재사용한다.

Circular Linked List는 아래와 같이 구성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
public class CircularLinkedList {
	Node mHead;
	Node mTail;
	
	int mCount = 0;
	
	CircularLinkedList(Node newNode) {
		mHead = newNode;
		mTail = newNode;
		mHead.setNext(mTail);
		mTail.setNext(mHead);
		
		mCount++;
	}
	
	public void addNode(Node newNode) {
		mTail.setNext(newNode);
		mTail = newNode;
		mTail.setNext(mHead);
		
		mCount++;
	}
		
	public void insertNode(Node newNode, int offset) {
		Node temp = mHead;
		
		for (int i = 1; i < offset; i++) {
			temp = temp.getNext();
		}
		
		newNode.setNext(temp.getNext());
		temp.setNext(newNode);
		
		mCount++;
	}
	
	public void deleteNode(int offset) {
		Node temp = mHead;
		Node delNode;
		
		for (int i = 1; i < offset - 1; i++) {
			temp = temp.getNext();
		}
		
		delNode = temp.getNext();
		temp.setNext(delNode.getNext());
		delNode = null;
		
		mCount--;
	}
	
	/*
	 * cycle : circular linked list를 몇 번 반복하여 출력할지 나타냄
	 */
	public void printNodes(int cycle) {
		Node temp = mHead;;
		
		for (int i = 0; i < mCount * cycle; i++) {
			System.out.print(temp.getData() + " ");
			temp = temp.getNext();
		}
		System.out.println();
	}
}

Main을 아래와 같이 구성할 경우, 결과는 아래와 같다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {
	public static void main(String[] args) {
		CircularLinkedList cll = new CircularLinkedList(new Node(1));
		
		cll.addNode(new Node(2));
		cll.addNode(new Node(3));
		cll.addNode(new Node(4));
		cll.addNode(new Node(5));
		cll.printNodes(1);
		cll.printNodes(2);
		
		cll.insertNode(new Node(8), 3);
		cll.printNodes(1);
		cll.printNodes(2);
		
		cll.deleteNode(2);
		cll.printNodes(1);
		cll.printNodes(2);
	}
}
1 2 3 4 5 
1 2 3 4 5 1 2 3 4 5 
1 2 3 8 4 5 
1 2 3 8 4 5 1 2 3 8 4 5 
1 3 8 4 5 
1 3 8 4 5 1 3 8 4 5

이중 Linked list (Doubly Linked List)

  • 앞 Node와 뒷 Node가 서로 바라보는 구조.

위에서 봤던 Linked list들과는 다르게 Previous Node도 설정한다.

역방향으로 출력하기 위해 print문을 하나 추가한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
public class DoublyLinkedList {
	Node mHead;
	Node mTail;
	
	int mCount = 0;
	
	DoublyLinkedList(Node newNode) {
		mHead = newNode;
		mTail = newNode;
		mHead.setNext(mTail);
		mTail.setPrevious(mHead);
		
		// for circular
		mHead.setPrevious(mTail);
		mTail.setNext(mHead);
		
		mCount++;
	}
	
	public void addNode(Node newNode) {
		mTail.setNext(newNode);
		newNode.setPrevious(mTail);
		mTail = newNode;
		
		// for circular
		newNode.setNext(mHead);
		mHead.setPrevious(newNode);
		
		mCount++;
	}
	public void insertNode(Node newNode, int offset) {
		Node temp = mHead;
		
		for (int i = 1; i < offset; i++) {
			temp = temp.getNext();
		}
		
		newNode.setNext(temp.getNext());
		newNode.setPrevious(temp);
		
		temp.getNext().setPrevious(newNode);
		temp.setNext(newNode);
		
		mCount++;
	}
	
	public void deleteNode(int offset) {
		Node temp = mHead;
		Node delNode;
		
		for (int i = 1; i < offset - 1; i++) {
			temp = temp.getNext();
		}
		
		delNode = temp.getNext();
		temp.setNext(delNode.getNext());
		
		delNode.getNext().setPrevious(temp);
		
		delNode = null;
		
		mCount--;
	}
	
	public void printNodesFront() {
		Node temp = mHead;
		
		for (int i = 0; i < mCount; i++) {
			System.out.print(temp.getData() + " ");
			temp = temp.getNext();
		}
		System.out.println();
	}
	public void printNodesBack() {
		Node temp = mHead;
		
		for (int i = 0; i < mCount; i++) {
			System.out.print(temp.getData() + " ");
			temp = temp.getPrev();
		}
		System.out.println();
	}
}

Main은 아래와 같이 구성한다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Main {
	public static void main(String[] args) {
		DoublyLinkedList dll = new DoublyLinkedList(new Node(1));
		
		dll.addNode(new Node(2));
		dll.addNode(new Node(3));
		dll.addNode(new Node(4));
		dll.addNode(new Node(5));
		dll.printNodesFront();
		dll.printNodesBack();
		
		dll.insertNode(new Node(8), 3);
		dll.printNodesFront();
		dll.printNodesBack();
		
		dll.deleteNode(2);
		dll.printNodesFront();
		dll.printNodesBack();
	}
}

결과는 아래와 같다.

1 2 3 4 5 
1 5 4 3 2 
1 2 3 8 4 5 
1 5 4 8 3 2 
1 3 8 4 5 
1 5 4 8 3

참조

Share