双向链表list

List是一个双向链表，可以在常数时间内插入和删除，不支持数组表示法和随机访问。

1.C++ list api说明

C++之list api介绍
1.定义一个双向链表first和second，类型是double
std::list first, second;

2.合并双向链表
first.merge(b):
说明：将链表b与调用链表first合并，合并之前，两个链表必须是已经排序，合并后经过排序的链表被保存在调用链表中，b链表为空；

3.链表删除结点
first.remove(val);
说明：从链表中删除val的所有结点。

3.链表插入 *** 作
first.splice(pos, b);
说明：将链表b的内容插入pos的前面，b为空。

4.链表翻转
first.reverse();
说明：将链表翻转

5.链表排序
first.sort();
说明：将链表排序

6.链表去重复
first.unique();
说明：将连续的相同元素压缩为单个元素。不连续的相同元素无法压缩，因此一般先排序，后去重 *** 作。

7.从链表头插入结点
first.push_front(x);

8.从链表尾插入结点
first.push_back(x);

9.从链表头出栈

first.pop_front();

10.从链表尾出栈
first.pop_back();

11.返回链表头
first.front();

12.返回链表尾
first.back()

13.链表插入 *** 作
first.inset(p, t);
说明：在p结点之前插入t结点。

14.删除结点
first.erase(p)
说明：删除结点p

15.清空链表
first.clear();

2.list之merge

#include 
#include 

// compare only integral part:
bool mycomparison (double first, double second){
	return (int(first) < int(second));
}

int main (){
  std::list first, second;

  first.push_back (3.1);
  first.push_back (2.2);
  first.push_back (2.9);

  second.push_back (3.7);
  second.push_back (7.1);
  second.push_back (1.4);

  first.sort();
  second.sort();

  first.merge(second);

  // (second is now empty)

  second.push_back (2.1);

  first.merge(second,mycomparison);

  std::cout << "first contains:";
  for (std::list::iterator it=first.begin(); it!=first.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}

3.list之push_back尾插法

#include 
#include 

int main (){
  std::list mylist;
  int myint;

  std::cout << "Please enter some integers (enter 0 to end):\n";

  do {
    std::cin >> myint;
    mylist.push_back (myint);
  } while (myint);

  std::cout << "mylist stores " << mylist.size() << " numbers.\n";

  return 0;
}

4.list之reverse链表逆序

#include 
#include 

int main (){
  std::list mylist;

  for (int i=1; i<10; ++i) mylist.push_back(i);

  mylist.reverse();

  std::cout << "mylist contains:";
  for (std::list::iterator it=mylist.begin(); it!=mylist.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << '\n';

  return 0;
}

5.list之push_back头插法

#include 
#include 

int main (){
  std::list mylist (2,100);         // two ints with a value of 100
  mylist.push_front (200);
  mylist.push_front (300);

  std::cout << "mylist contains:";
  for (std::list::iterator it=mylist.begin(); it!=mylist.end(); ++it)
    std::cout << ' ' << *it;

  std::cout << '\n';
  return 0;
}

5.list之sort排序

#include 
#include 
#include 
#include 

// comparison, not case sensitive.
bool compare_nocase (const std::string& first, const std::string& second)
{
  unsigned int i=0;
  while ( (itolower(second[i])) return false;
    ++i;
  }
  return ( first.length() < second.length() );
}

int main (){
  std::list mylist;
  std::list::iterator it;
  mylist.push_back ("one");
  mylist.push_back ("two");
  mylist.push_back ("Three");

  mylist.sort();

  std::cout << "mylist contains:";
  for (it=mylist.begin(); it!=mylist.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  mylist.sort(compare_nocase);

  std::cout << "mylist contains:";
  for (it=mylist.begin(); it!=mylist.end(); ++it)
    std::cout << ' ' << *it;
  std::cout << '\n';

  return 0;
}