LinkedListについて

[keitin]

p184

問題

ソートされていない連結リストから、重複する要素を削除するコードを書いて下さい。

解答

public static void deleteDups(LinkedListNode n) {
    Hashtable table = new Hashtable();
    LinkedListNode previous = null;
    while (n != null) {
      if (table.containsKey(n.data)) {
        previous.next = n.next;
      } else {
        table.put(n.data, true);
        previous = n;
      }
      n = n.next;
    }
  }

[keitin]

質問
LinkedListNodeというクラスJavaのリファレンスに乗ってないように思うのだけど
これは自作したクラスなのかね？

LinkedListというクラスはあるんご
http://docs.oracle.com/javase/jp/7/api/

[keitin]

LinkedListを使ってる良いサンプルコード無いかね？

[keitin]

import java.util.Hashtable

class LinkedList<E> {

  static class LinkedListNode<E> {
    E data;
    LinkedListNode<E> next;
  }

  LinkedListNode<E> head;
  LinkedListNode<E> tail;

  public LinkedList() {
    this.head = new LinkedListNode<E>();
    this.tail = new LinkedListNode<E>();
    head.next = tail;
  }

  public void addLast(E e) {
    LinkedListNode<E> node = new LinkedListNode<E>();
    tail.data = e; //既に末尾の要素はこの処理によって末尾の一つ前の要素になる
    tail.next = node; //こうすることでやっぱりtail.dataはnullになる
    tail = node; //末尾の要素の更新
  }

  public void addFirst(E e) {
    LinkedListNode<E> node = new LinkedListNode<E>();
    node.data = e;
    node.next = head.next;
    head.next = node;
  }

  static <E> E deleteNode(LinkedListNode<E> node) {
    if (node == null || node.next == null) {
      return null;
    }

    E deletedNode = node.data;
    LinkedListNode<E> nextNode = node.next;
    node.data = nextNode.data;
    node.next = nextNode.next;
    return deletedNode;
  }

  public E deleteFirst() {
    LinkedListNode<E> first = head.next;
    head.next = first.next;
    return first.data; //削除されるノード head自体はいじってないから相変わらずhead.dataはnull
  }

  public LinkedListNode<E> findFirst(E e) {
    LinkedListNode<E> curr = head.next;
    while (curr != null) {
      System.out.println(curr.data);
      if (curr.data != null && curr.data.equals(e)) {
        return curr;
      }
      curr = curr.next;
    }
    return null;
  }

  public void print() {
    LinkedListNode<E> node = head.next;
    while (node.next != null) {
      System.out.println(node.data);
      node = node.next;
    }
  }

  //重複している要素を削除
  public void deleteDups() {
    LinkedListNode<E> node = head.next;
    LinkedListNode<E> previous = null;
    Hashtable table = new Hashtable();
    while (node != null) {
      if (table.containsKey(node.data)) {
        previous.next = node.next;
      } else {
        table.put(node.data, true);
        previous = node;
      }
      node = node.next;
    }
  }

}



class LinkedListNodeSample {
  public static void main(String[] args) {
    LinkedList<String> list = new LinkedList<String>();
    list.addLast("hoge");
    list.addLast("piyo");
    list.addFirst("hooo");
    list.addFirst("kei");

    list.print();
  }
}


/*
連結リストの先頭と末尾はnullになっている！
(headとtailのdataはnil!)
*/

[keitin]

理解したあああ！
単方向連結リストこんなかんじかああ

[TakefumiYamamura]

質問
LinkedListNodeというクラスJavaのリファレンスに乗ってないように思うのだけど
これは自作したクラスなのかね？

まずこれは自作じゃなくて、もともとあるやつだね！
https://msdn.microsoft.com/ja-jp/library/ahf4c754(v=vs.110).aspx

ノード自体に格納している値と、その前とその後ろのノードをプロパティとしてもっている双方向のリストのノード（一つの要素）だね！

[TakefumiYamamura]

http://www.bogotobogo.com/cplusplus/linkedlist.php

こっちはcでいいかんじのやつがのっておる！

どのみち自分一人で一回何も見ずに実装した方がよさそうやね！

[keitin]

てんきゅうう！

[keitin]

//後ろからk番目の要素を取得
  public LinkedListNode<E> getAtIndexFromLast(int index) {
    LinkedListNode<E> node = head.next;
    int count = 0;
    while (node != null) {
      count++;
      node = node.next;
    }
    node = head.next;
    for (int i = 1; i < count - index; i++) {
      node = node.next;
    }
    return node;
  }

[tatsuki-m]

質問なのですが、
LinkedListNodeのEって何を指しているのでしょうか？？

[keitin]

@tatsuki-m
EはElementで、インスタンス初期化時に具体的な型を指定してあげればその方をdataに保持できるようになる！Swiftのジェネリクスんご

LinkedList<Integer> list = new LinkedList<Integer>();

[TakefumiYamamura]

#include <iostream>

using namespace std;

struct Node
{
    Node *next;
    int data;
};


class LinkedList {
public:
    Node *head;
    LinkedList(int data);
    ~LinkedList();
    void show();
    void addEnd(int data);
    void addNth(int data, int n);
    void deleteNth(int n);
};


LinkedList::LinkedList(int data) {
    head = (struct Node *)malloc( sizeof(struct Node) );
    head->next = NULL;
    head->data = data;
}

LinkedList::~LinkedList(){

}


void LinkedList::show(){
    Node *cur = head;
    int index = 0;
    while(cur != NULL){
        cout << "index: "<< index << "value: " << cur->data << endl; 
        cur = cur->next;
        index++;
    }
    return;
}


void LinkedList::addEnd(int data){
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;

    Node *cur = head;

    while(cur){
        if(cur->next == NULL){
            cur->next = newNode;
            return;
        }
        cur = cur->next;

    }

}

void LinkedList::addNth(int data, int n){
    Node *newNode = new Node;
    newNode->data = data;
    newNode->next = NULL;

    Node *cur = head;

    int index = 0;

    if(n == 0){
        newNode->next = cur;
        head = newNode;
    }

    while(cur){
        if(cur->next == NULL){
            if(index <= n) cout << "position is excess the length of list" << endl;
            return;
        }
        if(index == n-1){
            Node *tmpNode = new Node;
            tmpNode = cur->next;
            cur->next = newNode;
            newNode->next = tmpNode;
        }
        index++;
        cur = cur->next;
    }

}

void LinkedList::deleteNth(int n){
    Node *cur = head;

    if(n == 0){
        Node *tmp = new Node;
        tmp = head->next;
        delete head;
        head = tmp;
    }

    int index = 0;

    while(cur){
        if(cur->next == NULL){
            if(index <= n) cout << "position is excess the length of list" << endl;
            return;
        }
        if(index == n-1){
            Node *tmpNode = new Node;
            tmpNode = cur->next;
            if(cur->next->next != NULL) cur->next = cur->next->next;
            delete(tmpNode);
        }
        index++;
        cur = cur->next;
    }

}


int main(){
    LinkedList list = LinkedList(10);
    list.addEnd(20);
    list.addEnd(30);
    list.addEnd(40);
    list.show();
    cout << "----------------" << endl;
    list.addNth(100, 2);
    list.show();
    cout << "----------------" << endl;
    list.addNth(0,0);
    list.show();
    cout << "----------------" << endl;
    list.deleteNth(2);
    list.show();

}