📚 Linked List

Linked List는 기존 Array의 단점인, '생성 시 크기를 지정해줘야 함' 을 해결하기 위해 고안된 자료구조이다. 저장 공간만 충분하다면 크기가 무한한 리스트를 만들 수 있고, 이를 활용한 다양한 자료구조도 있기 때문에 중요도가 높은 자료구조이다.

그림과 같은 개념인데, 이를 위해서는 '노드' 라는 개념이 필요하다. 각 노드는 데이터를 담는 부분과 다음 노드를 가리키는 포인터 부분으로 구분할 수 있다.

📚 Functions

• insertAtFront
  : 리스트의 제일 앞에 요소를 삽입하는 기능
• deleteAtFront
  : 리스트의 제일 앞에서 요소를 제거하는 기능
• insertAtEnd
  : 리스트의 가장 끝에 요소를 삽입하는 기능
• isEmpty
  : 리스트가 비었는지 확인하는 기능
• getIter
  : 리스트를 순회하는 Iterator를 생성하는 기능

이 중 Iterator에 대해 자세히 말하자면, 연결 리스트를 Array처럼 처음부터 끝까지 순회하고 싶다고 하자. 인덱싱 느낌으로 !

for (int i=0;i<n;i++)(
arr[i] ...
}

// Linked List 순회하기
for (Iterator i=list.getIter();!i.atEnd();i.next())
...

이런 식으로 순회가 가능한 Iterator를 만들어볼 수 있다.

⌛️ 시간 복잡도

탐색의 경우, 연결 리스트에서는 요소를 찾기 위해 전부 순회하는 방법밖에 없으므로 O(n)의 시간복잡도가 주어진다.
삽입은 노드의 포인터만 연결해주면 되므로 O(1)의 시간복잡도가 주어진다.
삭제 또한 노드의 포인터만 제거해주면 되므로 O(1)의 시간복잡도가 주어진다.

리스트의 정렬을 위해 시간이 많이 소요되기 때문에, 보통 정렬에 대한 고려는 하지 않는 편이다.

💻 구현

Node

우선 노드는 다음과 같이 구현한다.
data와 포인터를 public으로 한 점에서 OOP 원칙을 위반하긴 하지만, 편안한 구현을 위해 이정도는 넘어가자.

class Node<T> {
	public T data;
	public Node<T> next;
}

Linked List

본격적으로 LinkedList 구현을 진행하자. 해당 자료형은 뒤에서도 많이 쓸 것이므로 제너릭 문법을 사용해서 구현한다.
구현에 따라 last 변수를 필요로 하지 않는 버전도 있고 한데, 본인은 우선 last를 포함해서 insertAtEnd도 가능한 버전으로 구현하였다.

deleteAtEnd를 구현하지 않는 이유는 그러면 last 이전의 포인터까지 필요하게 되는데, 여러모로 복잡해지기 때문. 구현하려면 변수 추가나 순회 등으로 구현할 수 있다. 아마 그러면 시간복잡도를 위해 변수 추가가 낫겠지?

class LinkedList<T> {
	private Node<T> first;
	private Node<T> last;

	public LinkedList() {
		this.first = null;
		this.last = null;
	}

	public void insertAtFront(T x) {
		Node<T> newNode;

		newNode = new Node<T>();
		newNode.data = x;
		newNode.next = first;
		first = newNode;
		if (isEmpty())
			last = newNode;
	}

	public T deleteAtFront() {
		T tmp;

		tmp = first.data;

		first = first.next;
		if (isEmpty())
			last = null;
		return tmp;
	}

	public void insertAtEnd(T x) {
		Node<T> newNode;

		newNode = new Node<T>();
		newNode.data = x;
		newNode.next = null;
		if (isEmpty())
			first = newNode;
		else
			last.next = newNode;
		last = newNode;
	}

	public Iter<T> getIter() {
		return (new Iter<T>(this, first));
	}

	public boolean isEmpty() {
		return (first == null || last == null);
	}
}

Iter

Iterator는 아래처럼 구현해준다.
자체적으로 링크드리스트를 가리키고 있어야 순회가 가능하고, 현재 위치를 기억해야 하므로 cur 변수를 만들어준다.
나머지 기능은 간단하다. 현재 값을 가져오는 getValue, 다음 노드로 넘어가는 next, 리스트의 끝에 도달했는지 판단하는 atEnd이다.

class Iter<T> {
	private LinkedList<T> l;
	private Node<T> cur;

	public Iter(LinkedList<T> l, Node<T> first) {
		this.l = l;
		this.cur = first;
	}

	public T getValue() {
	    if (atEnd()) return null;
		return (cur.data);
	}

	public void next() {
		if (atEnd()) return ;
		cur = cur.next;
	}

	public boolean atEnd() {
		return (cur == null);
	}
}

추가적으로, Iter를 활용해서 insertAfter, insertBefore와 deleteAfter, deleteBefore을 구현할 수 있다. 다만 이 경우에는 Iterator가 여러 개 생성되었을 때 가리키고 있는 노드가 삭제될 수 있다. 현존하는 자료구조 라이브러리에서조차 이에 대한 행동 정의를 거의 하지 않는데, 구현이 여러모로 복잡하기도 하고, 굳이 Iterator를 그렇게 여러 개씩 사용할 일이 그렇게 많지는 않아서인 것 같다.

이번 기회에 삭제에 대한 안전성을 보호하는 Iterator까지 구현해보도록 하자.
기본 개념은 생성된 Iterator를 저장하는 LinkedList 내부변수를 만들어서, 삭제 시마다 검사하여 해당 노드를 가리키고 있으면 다음 노드로 강제로 이동시키도록 한다.

이 경우 삭제의 시간복잡도는 총 Iterator의 갯수가 되니까 상승하겠지만, Iterator를 몇백 개씩 쓸 계획은 아직 없으니.

그러면 우선 Node, LinkedList, Iter 전부 바꿔줘야 한다.

노드 - prev 변수 추가

class Node<T> {
	public T data;
	public Node<T> next;
	public Node<T> prev;
}

노드부터 Doubly Linked List를 구현할 준비를 해주자.

Linked List - prev 처리

Linked List는 Doubly Linked List로, 이전 노드와의 연결 또한 만들어줘야 한다.
또한 체크를 위해 printAll과 printRev도 만들어주었다.

	class LinkedList<T> {
	private Node<T> first;
	private Node<T> last;

	public LinkedList() {
		this.first = null;
		this.last = null;
	}

	public void insertAtFront(T x) {
		Node<T> newNode;

		newNode = new Node<T>();
		newNode.data = x;
		newNode.next = first;
		newNode.prev = null;
		if (!isEmpty())
			first.prev = newNode;
		else 
			last = newNode;
		first = newNode;
	}

	public T deleteAtFront() {
		T tmp;

		tmp = first.data;

		first = first.next;
		if (isEmpty())
			last = null;
		else
			first.prev = null;
		return tmp;
	}


	public T deleteAtEnd() {
		T tmp;

		tmp = last.data;
		last = last.prev;
		if (isEmpty())
			first = null;
		else
			last.next = null;
		return tmp;
	}

	public void insertAtEnd(T x) {
		Node<T> newNode;

		newNode = new Node<T>();
		newNode.data = x;
		newNode.next = null;
		newNode.prev = last;
		if (isEmpty())
			first = newNode;
		else
			last.next = newNode;
		last = newNode;
	}

	public Iter<T> getIter() {
		return (new Iter<T>(this, first));
	}

	public boolean isEmpty() {
		return (first == null || last == null);
	}

	public void printAll() {
		for (Iter<T> i=this.getIter();!i.atEnd();i.next())
			System.out.print(i.getValue() + " ");
		System.out.println();
	}


	public void printRev() {
		Node<T> tmp = last;
		while (tmp != null) {
			System.out.print(tmp.data + " ");
			tmp = tmp.prev;
		}
		System.out.println();
	}
	public Node<T> getLast() {
		return (last);
	}

	public Node<T> getFirst() {
		return (first);
	}
}

내친 김에 deleteAtEnd도 구현해버렸다. doubly linked list여야 구현하기 쉽다.

Iter 처리 - 안전 삭제 구현 및 prev 처리

클래스에 정적 변수로 Iter를 담는 링크드 리스트를 만들어주고, 삭제 시마다 리스트를 순회하며 삭제할 노드를 가리키고 있는 Iterator를 다음으로 넘겨주었다.

class Iter<T> {
	private LinkedList<T> l;
	private Node<T> cur;
	private static LinkedList<Iter> Iters;

	public Iter(LinkedList<T> l, Node<T> first) {
		this.l = l;
		this.cur = first;
		if (Iters == null)
			Iters = new LinkedList<Iter>();
		else
			Iters.insertAtFront(this);
	}

	public T getValue() {
    	if (atEnd()) return null;
		return (cur.data);
	}

	public void next() {
		if (atEnd()) return ;
		cur = cur.next;
	}

	public boolean atEnd() {
		return (cur == null);
	}

	public void insertAfter(T x) {
		Node<T> newNode;

		if (atEnd()) return ;
		if (cur.next == null)
			l.insertAtEnd(x);
		else {
			newNode = new Node<T>();
			newNode.data = x;
			newNode.next = cur.next;
			newNode.prev = cur;
			cur.next.prev = newNode;
			cur.next = newNode;
		}
	}

	public void insertBefore(T x) {
		Node <T> newNode;

		if (atEnd()) return;
		if (cur.prev == null)
			l.insertAtFront(x);
		else {
			newNode = new Node<T>();
			newNode.data = x;
			newNode.next = cur;
			newNode.prev = cur.prev;
			cur.prev = newNode;
			cur.prev.next = newNode;
		}
	}

	public T delete() {
		if (atEnd()) return null;
		T tmp;

		for (Iter<Iter> i=Iters.getIter();!i.atEnd();i.next()) {
			if (i.getValue().atEnd()) continue;
			if (i.getValue().cur == this.cur)
				i.cur.data.next();
		}

		tmp = cur.data;

		if (cur.prev == null)
			l.deleteAtFront();
		else if (cur.next == null)
			l.deleteAtEnd();
		else {
			cur.prev.next = cur.next;
			cur.next.prev = cur.prev;
		}
		return tmp;
	}
}

테스트

간단한 코드를 짜서 안전삭제에 대해 체크했다.

class main {
	public static void main(String[] args) {

		LinkedList<Integer> l = new LinkedList<Integer>();
		l.insertAtEnd(1);
		l.insertAtEnd(2);
		l.insertAtEnd(3);

		System.out.print("Current List : ");
		l.printAll();

		System.out.print("Reverse : ");
		l.printRev();
		Iter<Integer> i = l.getIter();
		Iter<Integer> i2 = l.getIter();

		System.out.println("i1 : " + i.getValue() + "  i2 : " + i2.getValue());
		System.out.println("deleting from i1");
		i.delete();
		System.out.print("After deletion : ");
		l.printAll();
		System.out.print("Reverse : ");
		l.printRev();

		System.out.println("i1 pointing : " +i.getValue());
		System.out.println("i2 pointing : " + i2.getValue());


		l = new LinkedList<Integer>();

		i = l.getIter();
		i2 = l.getIter();

		System.out.println("Testing on empty list");
		i.delete();
		System.out.println("i1 pointing : " +i.getValue());
		System.out.println("i2 pointing : " + i2.getValue());

	}
}

i1과 i2가 같은 노드를 가리키고 있었지만, i1에서 호출한 삭제 이후 i2도 다음 노드를 가리키고 있는 것을 볼 수 있다.
실험 성공 !

-------------- 수정사항 ------------------

시간복잡도가 전체 Iterator의 개수가 아니라 해당 노드를 가리키고 있는 Iterator의 갯수에 비례해야 한다는 추가조건.

그러기 위해서 데이터를 담고 있는 노드에 Iterator를 추가로 담는 LinkedList인 IterLL를 구현해서 넣어줬다.
이를 통해 해당 노드를 가리키고 있는 Iterator를 식별할 수 있다.

그래서 삭제가 일어날 경우, 순회를 통해 해당 노드를 가리키고 있는 Iterator 중에서 삭제를 수행할 Iterator를 제외한 것들을 다음 칸으로 옮겨주고, 현재 노드의 IterLL에서 지워준 다음에, 다음 노드의 IterLL에 추가한다.
그러면 삭제를 수행할 때마다 해당 노드를 가리키고 있는 Iter를 전체 검사한 후, 다음 칸으로 넘기기 때문에 Iter 전체 개수가 아닌 노드를 가리키고 있는 Iter의 개수에 비례하게 된다.

Node.java

class Node {
	public int data;
	public Node next;
	public Node prev;
	public IterLL Iters;

	public Node() {
		Iters = new IterLL();
	}
}

IterNode.java

class IterNode {
	public Iter data;
	public IterNode next;
	public IterNode prev;
}

IntLL.java

class IntLL {
	private Node first;
	private Node last;

	public IntLL() {
		this.first = null;
		this.last = null;
	}

	public void insertAtFront(int x) {
		Node newNode;

		newNode = new Node();
		newNode.data = x;
		newNode.next = first;
		newNode.prev = null;
		if (!isEmpty())
			first.prev = newNode;
		else 
			last = newNode;
		first = newNode;
	}

	public int deleteAtFront() {
		int tmp;

		tmp = first.data;

		first = first.next;
		if (isEmpty())
			last = null;
		else
			first.prev = null;
		return tmp;
	}


	public int deleteAtEnd() {
		int tmp;

		tmp = last.data;
		last = last.prev;
		if (isEmpty())
			first = null;
		else
			last.next = null;
		return tmp;
	}



	public void insertAtEnd(int x) {
		Node newNode;

		newNode = new Node();
		newNode.data = x;
		newNode.next = null;
		newNode.prev = last;
		if (isEmpty())
			first = newNode;
		else
			last.next = newNode;
		last = newNode;
	}


	public Iter getIter() {
		return (new Iter(this, first));
	}

	public boolean isEmpty() {
		return (first == null || last == null);
	}

Iter.java

class Iter {
	private IntLL l;
	public Node cur;

	public Iter(IntLL l, Node first) {
		if (l.isEmpty()) return ;
		this.l = l;
		this.cur = first;
		first.Iters.insertAtEnd(this);
	}

	public int getValue() {
		if (atEnd()) return -1;
		return (cur.data);
	}

	public void next() {
		if (atEnd()) return ;
		cur = cur.next;
	}

	public void moveOn() {
		if (atEnd()) return ;

		cur.Iters.delete(this);
		cur = cur.next;
		if (atEnd()) return ;
		cur.Iters.insertAtEnd(this);
	}

	public boolean atEnd() {
		return (cur == null);
	}

	public void insertAfter(int x) {
		Node newNode;

		if (atEnd()) return ;
		if (cur.next == null)
			l.insertAtEnd(x);
		else {
			newNode = new Node();
			newNode.data = x;
			newNode.next = cur.next;
			newNode.prev = cur;
			cur.next.prev = newNode;
			cur.next = newNode;
		}
	}

	public void insertBefore(int x) {
		Node newNode;

		if (atEnd()) return;
		if (cur.prev == null)
			l.insertAtFront(x);
		else {
			newNode = new Node();
			newNode.data = x;
			newNode.next = cur;
			newNode.prev = cur.prev;
			cur.prev = newNode;
			cur.prev.next = newNode;
		}
	}

	public int delete() {
		if (atEnd()) return -1;
		int tmp;

		for (IterLLIter i=cur.Iters.getIter();!i.atEnd();i.next()) {
			if (i.getValue() != null && i.getValue() != this)
				i.getValue().moveOn();
		}
		tmp = cur.data;

		if (cur.prev == null)
			l.deleteAtFront();
		else if (cur.next == null)
			l.deleteAtEnd();
		else {
			cur.prev.next = cur.next;
			cur.next.prev = cur.prev;
		}

		cur = cur.next;
		return tmp;
	}
}

IterLL.java

class IterLL {
	private IterNode first;
	private IterNode last;

	public IterLL() {
		this.first = null;
		this.last = null;
	}

	public void insertAtEnd(Iter x) {
		IterNode newNode;

		newNode = new IterNode();
		newNode.data = x;
		newNode.next = null;
		newNode.prev = last;
		if (isEmpty())
			first = newNode;
		else
			last.next = newNode;
		last = newNode;
	}

	public Iter deleteAtFront() {
		Iter tmp;

		tmp = first.data;
		first = first.next;
		if (first != null)
			first.prev = null;
		else
			last = null;
		return tmp;

	}

	public Iter deleteAtEnd() {
		Iter tmp;

		tmp = last.data;
		last = last.prev;
		if (isEmpty())
			first = null;
		else
			last.next = null;
		return tmp;
	}

	public Iter delete(Iter x) {
		IterNode tmp;

		tmp = first;
		while (tmp != null) {
			if (tmp.data == x) {
				if (tmp.prev == null)
					deleteAtFront();
				else if (tmp.next == null)
					deleteAtEnd();
				else {
					tmp.prev.next = tmp.next;
					tmp.next.prev = tmp.prev;
				}
				tmp = tmp.next;
				return x;
			}
		tmp = tmp.next;
		}
		return null;
	}

	public IterLLIter getIter() {
		return (new IterLLIter(this, first));
	}

	public boolean isEmpty() {
		return (first == null || last == null);
	}
}

IterLLIter.java

class IterLLIter {
	private IterLL l;
	private IterNode cur;

	public IterLLIter(IterLL l, IterNode first) {
		this.l = l;
		this.cur = first;
	}

	public Iter getValue() {
		if (atEnd()) return null;
		return (cur.data);
	}

	public void next() {
		if (atEnd()) return ;
		cur = cur.next;
	}

	public boolean atEnd() {
		return (cur == null);
	}

	public Iter delete() {
		if (atEnd()) return null;
		Iter tmp;

		tmp = cur.data;

		if (cur.prev == null)
			l.deleteAtFront();
		else if (cur.next == null)
			l.deleteAtEnd();
		else {
			cur.prev.next = cur.next;
			cur.next.prev = cur.prev;
		}
		return tmp;
	}
}

대부분의 코드는 겹치지만, 은근 번거로웠음 .