第 7 回 線形リスト

本日の内容

このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。

7-1. 線形リストの操作

線形リストとは図のような特殊な二分木でした。

線形リスト

値は葉にだけ入れられます。 左向きの枝には必ず葉が付きます。そして、特に、右の枝に付く葉には nil という値の葉が付きます。 このような構造にしておくと 「次の要素を取り出す」や、「今アクセスしている要素の隣に新しい要素を追 加」するなどは定数時間でできます。 但し、ランダムに「n 番目の値」を取り出すのは、順番 に走査しなければならないので、 On 程度の計算時間がかかります。 第 5 回でキュー、スタックを取り上げた際、 線形リストを利用しましたが、今回は線形リストをテーマにします。

さて、キューやスタックでは「次の値」という操作のみに注目していました。 一般に多くのデータを取り扱う場合、データをアクセスする統一的な手法があ ると便利です。 データは通常、繰り返し計算で順番にアクセスすることになります。 したがって、この「順番にアクセスする」という概念を抽象的にとらえると、 さまざまな大量データをアクセスする際に同じようなプログラムで処理できる ようになります。

要素を順番に取り出すための仕組みをイテレータ (Iterator 反復子) と呼びます。 これは要素を順々に指していくのでポインタのようなものになります。 プログラミング用語としてデータを指し示す「参照」「イテレータ」「ポイン タ」は次のような違いがあります。

参照

参照とは、特定のオブジェクトを指すもの。あるいは格納先のメモリの番 地。

Java 言語ではオブジェクトの変数は参照を行う変数になる。 そのため、オブジェクト型の変数宣言してもオブジェクトの実体は生成されな い。 オブジェクトを使うためには new 演算子とコンストラクタの組などを使って オブジェクトを生成し、変数から参照するようにする。 関数呼び出しや、変数の代入において、参照がコピーされるだけでオブジェク トがコピーされないことに注意する必要がある。

一方、 C++ では変数宣言すると、基本型だろうがオブジェクトだろうが、全 て実体が作られる。 そのため、参照の機能が必要なときは意識して使用する。 C++ の参照変数は「型&」の形で宣言する。但し、何も指していない参照 変数は作れない。 そのため、初期化を伴う変数宣言、あるいは、関数宣言中にしか使用できない。 参照を作られる側には特に演算子は必要ない。 そのため、この仕組みより関数の変数呼び出しが可能になる。 


#include <iostream>
int main(){
  int a=3;
  int& b=a;
  int& c=b;
  std::cout << a << b << c << std::endl;
  c=4;b=5;a=6;
  std::cout << a << b << c << std::endl;
}

C++ では関数呼び出しは通常値呼び出しになるため、オブジェクトを引数にし ても、オブジェクトがコピーされてしまう。 そのため、オブジェクトの変更を行わない場合でも通常は const 指定の参照 呼び出しを行う。 


#include <iostream>
class Test {
private:
  int x,y;
public:
  Test(int _x, int _y){x=_x;y=_y;}
  int getX() const {return x;}
  int getY() const {return y;}
};
void show(const Test& t){
  std::cout << t.getX() << t.getY() << std::endl;
}
int main(){
  Test test(1,2);
  show(test);
}
イテレータ(反復子 Iterator)
データの集まりに含まれる要素を参照する。 単なる要素の参照の他、「次の参照を求める」演算や、「データの終了」を調 べることが許されている。 for 文や while 文とともに利用することで、データすべてに対する処理を行 うことができる。
ポインタ
一般的なメモリ番地を扱う。当然参照やイテレータの機能も実現できる。 その他に加減乗除などの演算も可能。 C 言語ではポインタを使って様々なことを実現するが、なんでもできる点で抽 象度は低く、トラブルを招きやすい

今回はこのイテレータという概念を導入して、線形リストの操作を考えたいと 思います。 なお、このイテレータは線形リストのみならずさまざまな大量のデータを格納 するデータ構造で実現されています。

さて、線形リストについて次のような操作を行うことを考えます。

  1. リストの初期化
  2. 先頭の要素を指すイテレータを得る
  3. 最後の要素を指すイテレータを得る
  4. 要素を最後に足す
  5. 要素を先頭に足す
  6. リストが空かどうか調べる
  7. リストのサイズを調べる
  8. リスト同士の結合
  9. イテレータの指す値
  10. イテレータを隣の要素に
  11. イテレータの指す場所へ要素を挿入
  12. イテレータの指す場所の要素を削除

また、C++, Java とも、リストに関して整列(順番に並べること) という機能も用意されています。 原理は次回に解説しますが、今回は整列の使い方についても解説します。

C++ での実装

C++ ではすでに線形リストもそのイテレータも STL で提供されています。 したがって、上記の処理は特別なプログラムを組まなくても次のようにすれば 可能になります。以下はリストの中に文字列を入れる例です。

リストの初期化

#include <string>
#include <list>
typedef std::list<std::string> stringList;
stringList aList;
先頭の要素を指すイテレータを得る

stringList::iterator anIterator = aList.begin();
最後の要素の(次の)イテレータを得る

stringList::iterator anIterator = aList.end();
要素を最後に足す

aList.push_back(要素);
要素を先頭に足す

aList.push_front(要素);
リストが空かどうか調べる

aList.empty()
リストのサイズを調べる

aList.size()
リスト同士の結合

aList.insert(aList.end(),anotherList.begin(),anotherList.end())
イテレータの指す要素の値

*anIterator;
イテレータを隣の要素に

++anIterator;
イテレータの指す場所へ要素を挿入

aList.insert(anIterator,要素);
イテレータの指す場所の要素を削除

aList.erase(anIterator);
リストを整列

aList.sort();

例7-1


#include <string>
#include <iostream>
#include <list>
typedef std::list<std::string> stringList;
int main(){
  stringList aList;
  aList.push_back("abc");
  aList.push_back("def");
  aList.push_front("ghi");
  for(stringList::iterator anIterator = aList.begin();
                 anIterator != aList.end(); ++anIterator){
    std::cout << *anIterator << std::endl;
  }
  std::cout << "size = " << aList.size() << std::endl;
  aList.sort();
  while(!aList.empty()){
    std::cout << *(aList.begin()) << std::endl;
    aList.erase(aList.begin());
  }
}

例7-2

上の例では数の並び替えでは小さい順でしかできません。 しかし、様々な順序で並び替えたい場合もあります。 ここでは、任意の順番を与えて並び替えを行う例を示します。

整数を二進数に直した時、 1 となる桁の少ない順に数を並べることを考えま しょう。 例えば、 0 から 20 までだと次のようになります。

十進数二進数1 の数
000
111
2101
3112
41001
51012
61102
71113
810001
910012
1010102
1110113
1211002
1311013
1411103
1511114
16100001
17100012
18100102
19100113
20101002

したがって、 0 から 20 を並べると次のようになります。

0 個1 個2 個3 個4 個
0, 1, 2, 4, 8, 16, 3, 5, 6, 9, 10, 12, 17, 18, 20, 7, 11, 13, 14, 15

これを C++ で作るには、まずビットの数を計算する関数を書きます。 

#include <iostream>
int numOfBits(int n){
  int k=0;
  while(n>0){
    k+=n%2;
    n/=2;
  }
  return k;
}
int main(){
  for(int i=0; i<=20; ++i){
    std::cout << i << "  " << numOfBits(i) << std::endl;
  }
}

数を x, y とした時、 1 の数が x より y が大きい 時だけ true, そうでない時 false が返すような () オペレータをメソッドと してもつクラスを作ります。 但し、後で functional ヘッダファイル中の binary_function とシグネチャ を合わせる必要があるため、 int 型でも const の参照型にします。 


#include <iostream>
int numOfBits(int n){
  int k=0;
  while(n>0){
    k+=n%2;
    n/=2;
  }
  return k;
}
class CompBit {
public:
  bool operator()(const int& x, const int& y) const {
    return numOfBits(x)<numOfBits(y);
  }
};
int main(){
  CompBit c;  // 比較用オブジェクトの作成
  for(int i=0; i<=20; ++i){
    std::cout << i ;
    for(int j=0; j<=20; ++j){
      std::cout << "  " << c(i,j);
    }
    std::cout << std::endl;
  }
}

この CompBit クラスを利用して数を並べ替えます。 この時、functional をインクルードして CompBit を std::binary_function<int,int,bool> のサブク ラスにしておきます。 


#include <iostream>
#include <list>
#include <functional>
int numOfBits(int n){
  int k=0;
  while(n>0){
    k+=n%2;
    n/=2;
  }
  return k;
}
class CompBit : public std::binary_function<int,int,bool> {
public:
  bool operator()(const int& x, const int& y) const {
    return numOfBits(x)<numOfBits(y);
  }
};
template <typename T>
void showList(T& aList){
  for(typename T::iterator anIterator = aList.begin();
      anIterator != aList.end(); ++anIterator){
    std::cout << *anIterator << " ";
  }
  std::cout << std::endl;
} 
void horizonLine(){
  std::cout << "---------------------------------------" << std::endl;
}
int main(){
  CompBit c; // 比較用オブジェクトの作成
  std::list<int> aList;
  for(int i=0; i<=20; ++i){
    aList.push_back(i);
  }
  showList(aList);
  horizonLine(); 
  aList.sort(c); // 比較用オブジェクトを使ったソート
  showList(aList);
}

なお、template 内で T::iterator など、型の計算を示すためには typename を前に置く必要があります。 また、ここで showList の引数を const 宣言していないのは const 宣言した 引数に対する iterator は別の型(const_iterator)になってしまうからです。

注釈

なおこの比較専用のクラスをオブジェクトに対して作る場合、 private メン バへのアクセス権が欲しくなる場合があります。 このような場合、そのオブジェクトクラスに operator() を実装してしまう考 え方もありますが、比較するクラスのカプセル化の有無によって実装方法が異 なるのは不自然です。

このような場合、比較専用クラスに private メンバへのアクセスを特別に認 めてしまえば解決します。 そのため、元のオブジェクトのクラスに friend class でフレンド指定をしま す。 


#include <functional>
class Example {
private:
  int x;
  int y;
public:
  Example(int _x, int _y){x=_x; y=_y;}
  friend class CompExample;
};
class CompExample : public std::binary_function<Example,Example,bool> {
public:
  bool operator()(const Example& a, const Example& b) const {return a.y<b.y;}
};

例7-3

オブジェクトに対して順番に並べることを考えます。 この場合も例7-2のように別の比較クラスを与えれば可能になります。 但し、比較クラスを与えずとも < 演算子、つまり operator< をクラス に実装しておけば、比較クラスを指定しなくても良くなります。 ここでは座標を原点に近い順に並べる例を示します。 


#include <iostream>
#include <cmath>
#include <list>
class Point {
private:
  double x,y;
public:
  Point(double _x, double _y):x(_x),y(y){}
  double distance() const {return std::sqrt(x*x+y*y);}
  bool operator<(const Point& p) const { return distance()<p.distance();}
  friend std::ostream& operator<<(std::ostream& os, const Point& p);
};
std::ostream& operator<<(std::ostream& os, const Point& p){
  os << p.x << ',' << p.y;
  return os;
}
template <typename T>
void showList(T& aList){
  for(typename T::iterator i=aList.begin();
      i!=aList.end(); ++i){
    std::cout << *i << std::endl;
  }
}
int main(){
  std::list<Point> lp;
  lp.push_back(Point(1,0));
  lp.push_back(Point(3,4));
  lp.push_back(Point(2,5));
  lp.push_back(Point(1,1));
  lp.push_back(Point(0,2));

  showList(lp);
  std::cout << "-------------------------"
	    << std::endl;
  lp.sort();
  showList(lp);
}

Java での実装

Java では線形リストは java.util.LinkedList で提供されています。 これは、 iterator() メソッドをインプリメントしています。 なお、 C++ では Iterator はポインタと同じような文脈で作られてましたが、 Java では Iterator は一つのオブジェクトとして実装されます。

リストの初期化

import java.util.*;

LinkedList<String> aList = new LinkedList<String>();  // Java 5
LinkedList aList = new LinkedList();  // Java 1.4
先頭の要素を指すイテレータを得る

ListIterator<String> anIterator = aList.listIterator(); // Java 5
// listIterator() コンストラクタは aList の型 (LinkedList<String>)
// に従うので型の指定は不要
ListIterator anIterator = aList.listIterator(); // Java 1.4
最後の要素の(次の)イテレータを得る
一命令では存在しない。但し、 Java ではイテレータの比較はしないので、 番兵は必要ない。メソッドにより最後かどうか判定する。
要素を最後に足す

aList.addLast(要素);
要素を先頭に足す

aList.addFirst(要素);
リストが空かどうか調べる

aList.isEmpty()
リストのサイズを調べる

aList.size()
リスト同士の結合

aList.addAll(anotherList);
イテレータの指す要素の値を得て、イテレータを隣の要素に

String aString = anIterator.next(); // Java 5
Object anObject = anIterator.next(); // Java 1.4
イテレータの指す場所へ要素を挿入

anIterator.add(要素);
next() をする前のイテレータの指す場所の要素を削除

anIterator.remove();
リストを整列する

java.util.Collections.sort(aList);

なおイテレータに関する構文をあげましたが、 Java 5 でリスト全要素にアク セスしたい場合は foreach 構文を使用した方が簡潔で安全です。

例7-4

Java 5

import java.util.*;
class TestList {
    public static void main(String arg[]){
	LinkedList<String> aList
            = new LinkedList<String>();
	aList.addLast("abc");
	aList.addLast("def");
	aList.addFirst("ghi");
	for(String s : aList){ // foreach 構文
	    System.out.println(s);
	}
	System.out.println("size = " + aList.size());
	java.util.Collections.sort(aList);
	ListIterator<String> anIterator
              = aList.listIterator();
	while(!aList.isEmpty()){
	    System.out.println(anIterator.next());
	    anIterator.remove(); 
	    // Iterator のメソッドを使うので 
	    // foreach は使わない
	}
    }
}
Java 1.4

import java.util.*;
class TestList {
    public static void main(String arg[]){
	LinkedList aList = new LinkedList();
	ListIterator anIterator;
	aList.addLast("abc");
	aList.addLast("def");
	aList.addFirst("ghi");
	anIterator =aList.listIterator();
	while(anIterator.hasNext()){
	    String s = (String) anIterator.next();
	    System.out.println(s);
	}
	System.out.println("size = " + aList.size());
	java.util.Collections.sort(aList);
	anIterator = aList.listIterator();
	while(!aList.isEmpty()){
	    String s = (String) anIterator.next();
	    System.out.println(s);
	    anIterator.remove();
	}
    }
}

例7-5

ここでも例7-2同様に、 Java において、任意の順序を指定して並び替えを行 うことを考えましょう。 そのため、 Java ではまず、 1 の数を計算する関数を持つクラスを作ります。 


class CompBit {
    static int numOfBits(int n){
	int k=0;
	while(n>0){
	    k+=n%2;
	    n/=2;
	}
	return k;
    }
    public static void main(String[] args){
	for(int i=0; i<=20; i++){
	    System.out.println(i+"  "+numOfBits(i));
	}
    }
}

そして、java.util.Collections.sort() を使うため、java.util.Comparator インタフェースをインプリメントします。 Comparator インタフェースの定義は以下の通りです。

Java 5

public interface Comparator<T> {
  public int compare(T o1, T o2);
  public boolean equals(Object obj);
}
Java 1.4

public interface Comparator {
  public int compare(Object o1, Object o2);
  public boolean equals(Object obj);
}

したがって作成している CompBit クラスに Comparator インタフェースをイ ンプリメントするには compare メソッドと equals メソッドを実装します。

Java 5

class CompBit implements java.util.Comparator<Integer> {
    static int numOfBits(int n){
	int k=0;
	while(n>0){
	    k+=n%2;
	    n/=2;
	}
	return k;
    }
    public int compare(Integer o1, Integer o2){
	int r1=CompBit.numOfBits(o1);
	int r2=CompBit.numOfBits(o2);
	return (r1<r2)?-1:(r1==r2)?0:1;
    }
    public boolean equals(Object obj){
	return false;
    }
}
class TestComp {
    public static void main(String[] args){
	CompBit c=new CompBit();
	for(int i=0; i<=20; i++){
	    System.out.print(i);
	    for(int j=0; j<=20; j++){
		System.out.print(" "+c.compare(i,j));
	    }
	    System.out.println();
	}
    }
}
Java 1.4

class CompBit implements java.util.Comparator {
    static int numOfBits(int n){
	int k=0;
	while(n>0){
	    k+=n%2;
	    n/=2;
	}
	return k;
    }
    public int compare(Object o1, Object o2){
	int r1=CompBit.numOfBits(((Integer)o1).intValue());
	int r2=CompBit.numOfBits(((Integer)o2).intValue());
	return (r1<r2)?-1:(r1==r2)?0:1;
    }
    public boolean equals(Object obj){
	return false;
    }
}
class TestComp {
    public static void main(String[] args){
	CompBit c=new CompBit();
	for(int i=0; i<=20; i++){
	    System.out.print(i);
	    Integer anInteger=new Integer(i);
	    for(int j=0; j<=20; j++){
		System.out.print(" "+c.compare(anInteger, new Integer(j)));
	    }
	    System.out.println();
	}
    }
}

そして、線形リストに対して java.util.Collections.sort() で整列します。

Java 5

class CompBit implements java.util.Comparator<Integer> {
    static int numOfBits(int n){
	int k=0;
	while(n>0){
	    k+=n%2;
	    n/=2;
	}
	return k;
    }
    public int compare(Integer o1, Integer o2){
	int r1=CompBit.numOfBits(o1);
	int r2=CompBit.numOfBits(o2);
	return (r1<r2)?-1:(r1==r2)?0:1;
    }
    public boolean equals(Object obj){
	return false;
    }
}
class TestComp {
   private static <T> void showList(java.util.List<T> aList){
      for(T i : aList){
        System.out.print( i.toString() + " ");
      }
      System.out.println();
   }
   private static void horizonLine(){
	System.out.println("---------------------------------------");
   }    
    public static void main(String[] args){
	CompBit aComparator = new CompBit();
	java.util.LinkedList<Integer> aList
            = new java.util.LinkedList<Integer>();
	for(int i=0; i<=20; i++){
	    aList.addLast(i);
	}
        showList(aList);
        horizonLine();
	java.util.Collections.sort(aList, aComparator);
        showList(aList);
    }
}
Java 1.4

class CompBit implements java.util.Comparator {
    static int numOfBits(int n){
	int k=0;
	while(n>0){
	    k+=n%2;
	    n/=2;
	}
	return k;
    }
    public int compare(Object o1, Object o2){
	int r1=CompBit.numOfBits(((Integer)o1).intValue());
	int r2=CompBit.numOfBits(((Integer)o2).intValue());
	return (r1<r2)?-1:(r1==r2)?0:1;
    }
    public boolean equals(Object obj){
	return false;
    }
}
class TestComp {
    private static void showList(java.util.List aList){
	for(java.util.Iterator anIterator = aList.iterator();
	    anIterator.hasNext();){
	    System.out.print(anIterator.next().toString()+" ");
	}
	System.out.println();
    }  
    private static void horizonLine(){
	System.out.println("---------------------------------------");
    }
    public static void main(String[] args){
	CompBit aComparator = new CompBit();
	java.util.LinkedList aList = new java.util.LinkedList();
	for(int i=0; i<=20; i++){
	    aList.addLast(new Integer(i));
	}
        showList(aList);
        horizonLine();
	java.util.Collections.sort(aList, aComparator);
        showList(aList);
    }
}

例7-6

C++ と同様に、オブジェクトに対して順番に並べることを考えます。 この場合も別の比較クラスを与えれば可能になります。 但し、比較クラスを与えずとも java.lang.Comparable インタフェースを implement すれば比較クラスを指定しなくても良くなります。 具体的には、クラス宣言時に implements Comparable を指定し、 public int compareTo( ここでは例7-3 同様に座標を原点に近い順に並べる例を示します。 


import java.util.*;
class Point implements Comparable<Point>{
    double x;
    double y;
    public Point(double _x, double _y){ x=_x; y=_y;}
    public double distance(){return Math.sqrt(x*x+y*y);}
    public int compareTo(Point p){
	if(distance()==p.distance()){return 0;}
	if(distance()<p.distance()){ return -1;}
	return 1;
    }
    public String toString(){
	return Double.toString(x)+", "+Double.toString(y);
    }
}
class Test {
    private static <T> void showList(List<T> aList){
	for(T i : aList){
	    System.out.println(i.toString());
	}
    }
    public static void main(String[] args){
	LinkedList<Point> lp = new LinkedList<Point>();
	lp.addLast(new Point(1,0));
	lp.addLast(new Point(3,4));
	lp.addLast(new Point(2,5));
	lp.addLast(new Point(1,1));
	lp.addLast(new Point(0,2));
	
	showList(lp);
	System.out.println("-------------------------");
	Collections.sort(lp);
	showList(lp);
    }
}

C 言語での実装

C++ や Java では線形リストがあらかじめ用意されていましたが、 C 言語に はありません。そこで、ポインタや構造体を使って実現する必要があります。

線形リストでは左の枝には必ず値を持つ頂点が付くので、左の枝を作る代わり に値を直接入れることにします。 右の枝はそのまま別の頂点を指すことにしますので、頂点を作る構造体は、左 の枝を意味する場所には値を入れ、右の枝を表す場所には別の頂点へのポイン タを入れることにします。 線形リストの頂点の構造体を定義すると次のようになります。 


typedef struct lst {
  char *item;
  struct lst  *next;
} LIST;

このようにして作った構造体をメモリ上に作り、next フィールドに次の頂点 の番地を入れて連結します。 ところで、リストの最後の nil を含んだ葉も同じ頂点である必要があります。 そこで、 next フィールドに NULL が入っていることとして表現することにし ます。 すると、空のリストは NULL が入った頂点だけで表現することになります。 一方、プログラム内でリストを扱うには、先頭の頂点へのポインタを持ちます。 したがって、プログラムで空のリストを作るには、次のようにします。 


LIST *aNode = malloc(sizeof(LIST));
aNode->next=NULL;

先頭への要素の追加

線形リストの先頭に文字列の要素を付け足す関数 addfirst(LIST *firstNode, char *str) は次のよう処理を行います。


まず、C 言語は値呼出しなので、関数の引数に含まれている先頭の 頂点へのポインタ firstNode は変更できません。 これは先頭の頂点のアドレスは変更できないことを意味します。 ですから、新たな要素 *str は既存の頂点へ代入されることになります。 したがって、付け足すべき新たな頂点の領域を確保したら、この領域は既存の 現在の先頭の要素が入ることになります。 つまり、新しい頂点の領域を確保したらその頂点は二番目の頂点にな るようにします。

新しい頂点の next フィールドは三番目、つまり付け足す前では二番目の頂点 を指すようにします。これは付け足す前では先頭の next フィールドに入って いたアドレスになります。

したがって処理をまとめると次のようになります。

  1. 新しい頂点の領域を作る
  2. 先頭の頂点の内容(要素、次の頂点へのポインタ)を新しい頂点にコピーす る。
  3. 先頭の頂点の要素には付け足すべき要素を代入し、次の頂点へのポインタ には新しく確保した頂点の領域のアドレスを入れる。

int addfirst(LIST *firstNode, char *str){
   LIST *newNode;
   if((newNode=malloc(sizeof(LIST)))==NULL){
     return 0;
   }
   newNode->item = firstNode->item;
   newNode->next = firstNode->next;
   firstNode->item = str;
   firstNode->next = newNode;
   return 1;
}

最後への要素の追加

一方、リストの最後に文字配列の要素を付け足す関数 addend(LIST *firstNode, char *str) は、nil 頂点を探して、その頂点に新しい要素を入れ、新たに作っ た nil 頂点を指すようにします。 


int addend(LIST *firstNode, char *str){
  LIST *newNode, *p;
  if((newNode=malloc(sizeof(LIST)))==NULL){
    return 0;
  }
  p=firstNode;
  while(p->next != NULL){
    p = p->next;
  }
  p->item = str;
  p->next = newNode;
  newNode->next = NULL;
  return 1;
}

最初に付け加えるのと違い、リストすべての要素を見なければならないので、 計算時間が余計にかかっていることに注意して下さい。

指している頂点の削除

リストの各要素に対して、単純に指している頂点を削除すると、その頂点を指 す手前の頂点が次の頂点を指すようにできません。 そのため、特定の要素を消す場合、他の接続関係を調整してやる必要がありま す。 また、先頭の要素を連続して消したい場合を考えると、リストの先頭を指すデー タは消えても、領域が消えては次の先頭を探すことができません。 そのため、先頭の領域は消さず、その領域に次のデータが入っているようにす る必要があります。 したがって、領域としてはその次の頂点の領域を消すことにし、消 す前に次の頂点の持つ情報を現在指している領域にコピーすることとします。

  1. 消すべき領域である、次の頂点のアドレスを記憶する
  2. 現在の頂点の領域に、次の頂点の要素とポインタをコピーする
  3. 消すべき領域を消す 

void removenode(LIST *aNode){
  LIST *deleteNode = aNode->next;
  aNode->item = deleteNode->item;
  aNode->next = deleteNode->next;
  free(deleteNode);
}

サンプルコード


#include <stdio.h>
#include <stdlib.h>
typedef struct lst {
  struct lst  *next;
  char *item;
} LIST;
void addend(LIST *pointer, char *i){
  LIST *newnode=malloc(sizeof(LIST));
  newnode->next=NULL;
  while(pointer->next != NULL){
    pointer = pointer->next;
  }
  pointer->next=newnode;
  pointer->item=i;
}
void addfirst(LIST *pointer, char *i){
  LIST *newnode=malloc(sizeof(LIST));
  newnode->next=pointer->next;
  newnode->item=pointer->item;
  pointer->next=newnode;
  pointer->item=i;
}
int empty(LIST *pointer){
  return pointer->next == NULL;
}
int size(LIST *pointer){
  LIST *p=pointer;
  int i=0;
  while(p->next != NULL){
    p=p->next;
    i++;
  }
  return i;
}
void removeitem(LIST *pointer){
  LIST *d=pointer->next;
  pointer->item=d->item;
  pointer->next=d->next;
  /* free((pointer->next)->item) */
  free(d);
}
void showItem(LIST *p){
  while(p->next!=NULL){
    printf("%s\n",p->item);
    p=p->next;
  }
  printf("\n");
}
int main(void){
  LIST *firstNode=malloc(sizeof(LIST));
  firstNode->next=NULL;
  addend(firstNode,"abc");
  addend(firstNode,"def");
  addfirst(firstNode,"ghi");
  showItem(firstNode);
  printf("size = %d\n",size(firstNode));
  while(!empty(firstNode)){
    showItem(firstNode);
    removeitem(firstNode);
  }
  return 0;  
}

7-2. 線形リストと配列

線形リストも配列も複数のものを格納することができますが、それぞれにおい て処理の効率が変わります。 従って、用途に応じて選択する必要があります。

配列はメモリの連続した領域を確保し、 n 番目の要素へのアクセスを許しま す。 n 番目の要素へのアクセスは既に紹介したように、 (0 番目の要素のアドレス ) + n⨯ (要素のサイズ) でアドレスを計算します。 従って、時間計算量は n を計算する手間になります。 これは n の桁数に比例した時間かかります。 要素数が最大 N だとすると、全体の時間計算量は O( log N ) になります。 一方、特定の位置(先頭など)に要素を挿入したり、削除したりするには全部の 要素をずらす必要があります。 一つの要素をずらすのに定数時間で済んでも、最大で全要素数 N に比例する 時間だけかかります。 従って、全体の時間計算量は O( N ) になります。

線形リストでは n 番目の要素にアクセスするには、基本的には先頭から順に 見ていくしかありません。 従って、時間計算量は O( N ) になります。 しかし、一方、特定の位置に要素を挿入したり、削除したりするには、メモリ の適当な位置に頂点を確保し、リンクをつなげるだけなので、 O( 1 ) の時間計算量で済みます。

以上のように要素へのランダムアクセスが必要な時は配列、要素の追加、削除 が頻繁な時は線形リストが有利なことが分かります。

ランダムアクセス要素の追加、削除
配列 O( log N ) O( N )
線形リスト O( N ) O( 1 )

7-3. 双方向リスト

双方向リストとは、次の頂点へのポインタと前の頂点へのポインタの両方を保 持するものです。 特定の頂点に注目して処理する場合に便利です。 エディタなど、特定の行に注目した処理をするのに用いられます。 実は C++ の list, Java の LinkedList のどれも双方向リストです。 C++ では Iterator に対して -- 演算が可能です。 一方、Java では java.util.ListIterator には previous() メソッドが用意 されています。

演習7-1

双方向リストを使って less を作りなさい。 less とは more を拡張したコマンドで、次の動作をします。

  1. コマンドラインでファイル名を指定します。
  2. 先頭の 24 行を表示します。
  3. 空白か d の入力で次の 24 行を表示します。
  4. u の入力で前の 24 行を表示します。
  5. q の入力で終了します。
  6. < で先頭へ、 > で最後(から 24 行前)へ注目行を移動します。

コマンドラインでの指定法

main 関数を int main(int argc, char* argv[]) で指定すると、コマンドライ ンで文字列をプログラムに渡せるようになります。 コマンドラインになにも指定しないと、 argc が 1 になり、第二引数の char *argv[] の argv[0] に起動コマンド名が入ります。 起動時にコマンド(.\a.exe) の後ろに文字列を空白で区切ると、それぞれが argv[] の配列に入ります。

例7-7

#include <stdio.h>
int main(int argc, char * argv[]){
  int i;
  if(argc==1){
    printf("Usage: %s filename ...\n",argv[0]);
    return 2;
  }
  printf("起動コマンド %s\n",argv[0]);
  for(i=1;i<argc;i++){
    printf("引数 %d = %s\n",i,argv[i]);
  }
  return 0;
}

付録: C 言語での双方向リストの実装


#include <stdio.h>
#include <stdlib.h>
typedef struct blst {
  struct blst  *next;
  struct blst  *previous;
  char *item;
} BLIST;
int add(BLIST *base, BLIST *pointer, char *i){
  BLIST *newnode;
  if((newnode=malloc(sizeof(BLIST)))==NULL){
    return 0;
  }
  newnode->item = i;
  newnode->next = pointer->next;
  if(pointer->next == NULL){
    newnode->previous = base->previous;
    base->previous = newnode;
  }else{
    newnode->previous = (pointer->next)->previous;
    (pointer->next)->previous = newnode;
  }
  pointer->next = newnode;
  return 1;
}

void printlist(BLIST *base){
  BLIST *p=base;
  while((p=p->next)!=NULL){
    printf("%s ",p->item);
  }
  printf("\n");
}
void printreverse(BLIST *base){
  BLIST *p=base;
  while((p=p->previous)!=NULL){
    printf("%s ",p->item);
  }
  printf("\n");
}
int empty(BLIST *base){
  return base->next == NULL;
}
int size(BLIST *base){
  BLIST *p=base;
  int i=0;
  while((p=p->next) != NULL){
    i++;
  }
  return i;
}
int removenode(BLIST *base, BLIST *pointer){
  BLIST *p,*n;
  if(base==pointer){
    return 0;
  }
  p = pointer->previous;
  n = pointer->next;
  if(p==NULL){
    base->next = n;
  }else{
    p->next = n;
  }
  if(n==NULL){
    base->previous = p;
  }else{
    n->previous = p;
  }
  /* free(pointer->item) */
  free(pointer);
  return 1;
}
void showCondition(BLIST *bList){
  printlist(bList);
  printreverse(bList);
  printf("size = %d\n",size(bList));
}    
#define errorCheck(func) if(!(func))exit(1)
int main(void){
  BLIST *l;
  errorCheck((l=malloc(sizeof(BLIST)))!=NULL);
  BLIST *p;
  l->next=l->previous=NULL;
  errorCheck(add(l,l,"abc"));
  showCondition(l);
  errorCheck(add(l,l,"def"));
  showCondition(l);
  errorCheck(add(l,l->previous,"ghi"));
  showCondition(l);
  errorCheck(add(l,l->previous,"jkl"));
  showCondition(l);
  errorCheck(add(l,l->next->next->next,"mno"));
  showCondition(l);
  while(!empty(l)){
    showCondition(l);
    removenode(l, l->next);
  }
  return 0;
}
坂本直志 <sakamoto@c.dendai.ac.jp>
東京電機大学工学部情報通信工学科