2017-04-09 링크드 리스트
1. Javascript
<!DOCTYPE html><head> <meta charset="UTF-8"> <title>Title</title></head><script> //element: data, next: nextnode function Node(element){ this.element = element; this.next = null; } //초기 head.next는 null function LList(){ this.head = new Node("head"); this.find = find; this.insert = insert; this.remove = remove; this.display = display; this.findPrevious = findPrevious; } function find(item){ var currNode = this.head; while(currNode.element != item){ currNode = currNode.next; } return currNode; } function insert(newElement, item){ var newNode = new Node(newElement); var current = this.find(item); newNode.next = current.next; current.next = newNode; } function display(){ var currNode = this.head; while(!(currNode.next==null)){ console.log(currNode.next.element); currNode = currNode.next; } } function findPrevious(item){ var currNode = this.head; while(!(currNode.next == null) && (currNode.next.element != item)){ currNode = currNode.next; } return currNode; } function remove(item){ var prevNode = this.findPrevious(item); if(!(prevNode.next == null)){ prevNode.next = prevNode.next.next; } } var cities = new LList(); cities.insert("Conway","head"); cities.insert("Seoul","Conway"); cities.display();</script></text></span><br /></span></b></p><p style="margin-left: 4em;"><b><span style="font-size: 24pt;"><br /></span></b></p>
2. Java
- 링크드 리스트는 데이터 추가 삭제시에 효율적이다
- 메모리가 허용되는 한 계속 추가 할 수 있다
1. Node<T>.class
class Node<T> { private Node<T> nextRef; private T value; public void setValue(T value){ this.value = value; } public T getValue(){ return value; } public void setNextRef(Node<T> nextRef){ this.nextRef = nextRef; } public Node<T> getNextRef(){ return nextRef; } }
- 위에 있는 data/next의 한 블록을 노드라고 한다
- 링크드 리스트를 구현하기 위해선 노드가 필요하다
- data는 노드의 값이면 next는 다음 노드를 가르키기 위한 주소 값이 들어간다
2. SingleLinkedList<T>.class
1) 변수 정의
private Node<T> head;private Node<T> tail;private int size = 0;
- head, tail 객체를 선언한다. head와 tail은 노드의 추가 삭제시의 참고가 된다
- head, tail은 하나의 노드라기 보다는 노드들을 컨트롤 할 수 있는 설명서의 역할
- size는 엘리먼트의 크기를 나타 낸다
2) addLast(T element)
public void addLast(T element){ Node<T> newNode = new Node<T>(); newNode.setValue(element); System.out.println("adding:"+element); size++; if(head == null){ head = newNode; tail = newNode; }else{ //이 부분은 결국 앞 노드의 다음 노드를 가르키는 부분을 셋팅 하는 것과 같다 tail.setNextRef(newNode); tail = newNode; }}
- 노드를 뒤에서 추가한다
- 노드가 없을 시에 처음 head와 tail은 모두 처음 추가된 노드를 가르키게 된다
- 이후에 추가된 노드는 tail 값을 참조하여 추가한다
- 처음 추가된 노드가 얕은 복사(shallow copy) 과정이 일어나서 tail의 next값을 셋팅 하더라도 앞 노드의 다음 주소값을 셋팅 하는 효과가 일어난다
3) addFirst(T element)
public void addFirst(T element){ Node<T> newNode = new Node<>(); newNode.setValue(element); newNode.setNextRef(head); head = newNode; size++; //처음 노드 일 때 if(head.getNextRef() == null){ tail = newNode; }}
- head의 값을 참조 하여 앞에 노드를 추가한다
- 처음 노드가 추가 되는 거라면 tail을 새로운 노드로 지정
4) node(int x)
public Node<T> node(int x){ Node<T> temp = head; //인덱스 값을 바탕으로 탐색을 시작 for(int i = 0; i<x; i++){ temp = temp.getNextRef(); } return temp;}
- 특정 노드의 위치를 찾는 함수이다
- 이 함수를 이용하여 특정위치 추가/삭제 또는 데이터 가져오기가 가능하다
- head를 시작으로 계속 다음 노드 값을 추적하여 최종 인덱스 의 값을 찾는다
5) add(T element, int x)
public void add(T element,int index){ Node<T> newNode = new Node<>(); newNode.setValue(element); if(size == index + 1){ addLast(element); }else if(index == 0){ addFirst(element); }else{ Node<T> temp = node(index-1); newNode.setNextRef(temp.getNextRef()); temp.setNextRef(newNode); size++; if(newNode.getNextRef() == null){ tail = newNode; } } }
- 특정 위치에 노드를 삽입한다
- index - 1은 원하는 위치의 값은 바로 그 뒤의 노드가 알기 때문에 바로뒤의 노드를 이용하여 삽입한다
6) deleteFirst()
public Node<T> deleteFirst(){ Node<T> returnData = head; head = returnData.getNextRef(); System.out.println("deleteFirst:"+returnData.getValue()); size--; return returnData; }
- 앞의 노드 삭제
- head를 앞의 노드가 가르키는 값으로 지정한다
7) delete(int T)
public Node<T> delete(int element){ if(element == 0){ return deleteFirst(); } Node<T> temp = node(element-1); Node<T> deletedData = temp.getNextRef(); temp.setNextRef(temp.getNextRef().getNextRef()); size--; if(deletedData == tail){ tail = temp; } System.out.println("delete:" +deletedData.getValue()); return deletedData;}
- 특정 위치의 노드를 삭제한다
- node()를 이용하여 위치를 찾고 사이의 연결 고리를 이어준다
8) deleteLast()
public Node<T> deleteLast(){ return delete(size-1);}
- 마지막 노드 삭제
9) toString()
public String toString(){ if(head == null){ return "[]"; } Node<T> temp = head; String str = "["; while(temp.getNextRef() != null){ str += temp.getValue() + ","; temp = temp.getNextRef(); } str += temp.getValue(); return str+"]"; }
- 요소의 상태를 알 수 있도록 화면에 출력한다
10) get()
public T get(int x){ Node<T> temp = node(x); return temp.getValue();}
- 요소 값 가져오기
11) main()
public static void main(String[]args){ SingleLinkedList<Integer> node = new SingleLinkedList(); node.addLast(1); System.out.println(node); node.addLast(2); System.out.println(node); node.addLast(3); System.out.println(node); node.addFirst(9); System.out.println(node); node.addFirst(10); System.out.println(node); node.deleteLast(); System.out.println(node); node.deleteLast(); System.out.println(node); node.add(99, 1); System.out.println(node); node.add(100, 3); System.out.println(node); node.add(1000, 0); System.out.println(node); System.out.println(node.get(2));}
'etc > study' 카테고리의 다른 글
| 960 그리드 시스템 (0) | 2018.02.19 |
|---|---|
| 자바스크립트 클릭이벤트 click() (0) | 2018.02.09 |
| 요소 가운데 정렬 (0) | 2018.02.02 |
| [study] 2017-04-16 더블링크드리스트 (0) | 2017.04.16 |
리딩리드
