- 浏览: 2552167 次
- 性别:
- 来自: 成都
文章分类
最新评论
-
nation:
你好,在部署Mesos+Spark的运行环境时,出现一个现象, ...
Spark(4)Deal with Mesos -
sillycat:
AMAZON Relatedhttps://www.godad ...
AMAZON API Gateway(2)Client Side SSL with NGINX -
sillycat:
sudo usermod -aG docker ec2-use ...
Docker and VirtualBox(1)Set up Shared Disk for Virtual Box -
sillycat:
Every Half an Hour30 * * * * /u ...
Build Home NAS(3)Data Redundancy -
sillycat:
3 List the Cron Job I Have>c ...
Build Home NAS(3)Data Redundancy
Interview(3)Vector List
Stack and Queue are special sequences.
Stack - insert, remove and access only apply to top item
Queue - remove and access only apply to top item, insert apply to bottom item
Deque - insert, remove and access only apply to top/bottom items.
Rank - Vector - Array List
getSize()
isEmpty()
getAtRank(r) - 0<=r < getSize(), return item whose rank is r
replaceAtRank(r, e) - replace the item whose rank is r, return the original item
insertAtRank(r, e) - insert the item at rank r, move the r+ items
removeAtRank(r) - remove the item at rank r, move the r+ items
public class VectorArray implements Vector{
private final int N = 1024; //max size
private int n = 0; //count
private Object[] A; //array
public VectorArray(){
A = new Object[N];
n = 0;
}
public int getSize() { return n; }
public boolean isEmpty() { return (0 == n) ? true : false; }
public Object getAtRank(int r) //O(1)
throws ExceptionBoundaryViolation{
if (0>r || r >= n ) { throw new ExceptionBoundaryViolation(“Error: boundary over”); }
return A[r];
}
public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
if ( 0> r || r >= n) { throw new ExceptionBoundaryViolation(“Error: “); }
Object bak = A[r];
A[r] = obj;
return bak;
}
public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
if (0>r || r> n ) { throw new ExceptionBoundaryViolation(“Error”); }
if (n >= N) { throw new ExceptionBoundaryViolation(“Error"); }
for (int i = n; i> r; i—) { A[i] = A[i-1]; } //all the items behind r will move to r+1
A[r] = obj; // insert the object to rank r
n++; //update total size of the vector
return obj;
}
public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
if(0>r|| r>=n) { throw new ExceptionBoundaryViolation(“Error”); }
Object bak = A[r];
for (int i = r; i<n; i++) { A[i] = A[i+1]; } //
n- - ; //update the size of the vector
return bak;
}
}
O(N);
Extend the Size of the Vector
if n>=N, insertAtRank()
#1 Create a new 2N new array B
#2 Copy all elements in A[] to B[]
#3 Replace A back to B
public class VectorExtArray implements Vector {
private int N = 8; //initial capacity N
private int n;
private Object A[];
public VectorExtArray() {
A = new Object[N];
n = 0;
}
public int getSize() { return n; }
public boolean isEmpty() {
return (0 == n) ? true : false;
}
public Object getAtRank(int r) throws ExceptionBoundaryViolation {
if ( 0 > r || r >= n ) { throw new ExceptionBoundaryViolation(“Error”); }
return A[r];
}
public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
if ( 0 > r || r >= n ) { throw new ExceptionBoundaryViolation(“Error”); }
Object bak = A[r];
A[r] = obj;
return bak;
}
public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
if ( 0 > r || r > n) { throw new ExceptionBoundaryViolation(“Error”); }
if ( N <= n) {
N * = 2;
Object B[] = new Object[N]; // create a new array 2N
for ( int i = 0; i<n; i++) {
B[i] = A[i]; // copy all elements from A[] to B[]
}
A = B;
}
for(int i = n; i> r; i- - ) { A[i] = A[i -1]; }
A[r] = obj;//insert
n++;
return obj;
}
public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
if ( 0> r || r>=n) { throw new ExceptionBoundaryViolation(“Error”); }
Object bak = A[r];
for(int i = r; i< n-1; i++) { A[i] = A[i+1]; }
n- - ;
return bak;
}
}
java.util.ArrayList and java.util.Vector Classes
Vector is similar with ArrayList, but it is synchronized.
ArrayList is a better choice if your program is thread-safe.
Vector and ArrayList require space as more elements are added. Vector each time doubles its array size, while ArrayList grow 50% of its size each time.
ArrayList
methods - first(), last(), getPrev(p); getNext(p); replace(p, e); insertFirst(e); insertLast(e); insertBefore(p, e); insertAfter(p, e);
remove(p);
method: insertBefore(p, e)
inputs: position p, item e
outputs: insert item e before position p
{
create a new node v;
v.setElement(e); //store the item e in node v
v.setPrev(p.getPrev); //link the p’s prev
(p.getPrev()).setNext(v); //link p’s prev
p.setPrev(v); //p will be the next of v
return ((Position)v); //
}
insertAfter(), insertFirst(), insertLast will all be similar
remove(p) Algorithm
method: remove(p)
inputs: Position p
outputs: remove the item e in position p, return e
{
bak = p.element; // backup the current item
(p.getNext()).setPrev(p.getPrev); //link p’s next with p’s previous
(p.getPrev()).setNext(p.getNext);
p.setNext(null); //isolate item p
p.setPrev(null); //isolate item p
return bak;
}
Final List Implementation with Double End Node
public class ListDLNode implements List {
protected int numElem; //size of items
protected DLNode header, trailer; // first node and last node
public ListDLNode(){
numElem = 0; //empty
header = new DLNode(null, null, null); //first
trailer = new DLNode(null, header, null); //tailer
header.setNext(trailer); //link header and trailer
}
protected DLNode checkPosition(Position p) throws ExceptionPositionInvalid {
if (null == p){
throw new ExceptionPositionInvalid(“Error, position is null”);
}
if(header == p){
throw new ExceptionPositionInvalid(“Error, header is invalid position”);
}
if(trailer == p){
throw new ExceptionPositionInvalid(“Error, trailer is invalid position”);
}
DLNode temp = (DLNode)p;
return temp;
}
public int getSize() { return numElem; }
public boolean isEmpty() { return (numElem == 0); }
public Position first() throws ExceptionListEmpty {
if(isEmpty()){
throw new ExceptionListEmpty(“Error: empty list”);
}
return header.getNext();
}
public Position last() throws ExceptionListEmpty {
if(isEmpty()){
throw new ExceptionListEmpty(Error: empty list“");
}
return trailer.getPrev();
}
public Position getPrev(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation{
DLNode v = checkPosition(p);
DLNode prev = v.getPrev();
if(prev == header){
throw new ExceptionBoundaryViolation(“error: reach the header of list”);
}
return prev;
}
public Position getNext(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation {
DLNode v = checkPosition(p);
DLNode next = v.getNext();
if(next == trailer){
throw new ExceptionBoundaryViolation(“error: reach the trailer”);
}
return next;
}
public Position insertBefore(Position p, Object element) throws ExceptionPositionInvalid {
DLNode v = checkPosition(p);
numElem++;
DLNode newNode = new DLNode(element, v.getPrev(), v);
v.getPrev().setNext(newNode);
v.setPrev(newNode);
return newNode;
}
public Position insertAfter(Position p, Object element) throws ExceptionPositionInvalid {
DLNode v = checkPosition(p);
numElem++;
DLNode newNode = new DLNode(element, v, v.getNext());
v.getNext().setPrev(newNode);
.vsetNext(newNode);
return newNode;
}
public Position insertFirst(Object e){
numElem++;
DLNode newNode = new DLNode(e, header, header.getNext());
header.getNext().setPrev(newNode);
header.setNext(newNode);
return newNode;
}
public Position insertLast(Object e) {
numElem++;
DLNode newNode = new DLNode(e, trailer.getPrev(), trailer);
if(null == trailer.getPrev()) {
System.out.println(“!!!prev is null, that is impossible!!!");
}
trailer.getPrev().setNext(newNode);
trailer.setPrev(newNode);
return newNode;
}
public Object remove(Position p) throws ExceptionPositionInvalid {
DLNode v = checkPosition(p);
numElem- - ;
DLNode vPrev = v.getPrev();
DLNode vNext = v.getNext();
vPrev.setNext(vNext);
vNext.setPrev(vPrev);
Object vElem = v.getElem();
v.setNext(null);
v.setPrev(null)
return vElem;
}
public Object removeFirst() { return remove(header.getNext()); }
public Object removeLast() { return remove(trailer.getPrev()); }
public Object replace(Position p, Object obj) throws ExceptionPositionInvalid {
DLNode v = checkPosition(p);
Object oldElem = v.getElem();
v.setElem(obj);
return oldElem;
}
}
References:
https://stackoverflow.com/questions/2986296/what-are-the-differences-between-arraylist-and-vector
Stack and Queue are special sequences.
Stack - insert, remove and access only apply to top item
Queue - remove and access only apply to top item, insert apply to bottom item
Deque - insert, remove and access only apply to top/bottom items.
Rank - Vector - Array List
getSize()
isEmpty()
getAtRank(r) - 0<=r < getSize(), return item whose rank is r
replaceAtRank(r, e) - replace the item whose rank is r, return the original item
insertAtRank(r, e) - insert the item at rank r, move the r+ items
removeAtRank(r) - remove the item at rank r, move the r+ items
public class VectorArray implements Vector{
private final int N = 1024; //max size
private int n = 0; //count
private Object[] A; //array
public VectorArray(){
A = new Object[N];
n = 0;
}
public int getSize() { return n; }
public boolean isEmpty() { return (0 == n) ? true : false; }
public Object getAtRank(int r) //O(1)
throws ExceptionBoundaryViolation{
if (0>r || r >= n ) { throw new ExceptionBoundaryViolation(“Error: boundary over”); }
return A[r];
}
public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
if ( 0> r || r >= n) { throw new ExceptionBoundaryViolation(“Error: “); }
Object bak = A[r];
A[r] = obj;
return bak;
}
public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
if (0>r || r> n ) { throw new ExceptionBoundaryViolation(“Error”); }
if (n >= N) { throw new ExceptionBoundaryViolation(“Error"); }
for (int i = n; i> r; i—) { A[i] = A[i-1]; } //all the items behind r will move to r+1
A[r] = obj; // insert the object to rank r
n++; //update total size of the vector
return obj;
}
public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
if(0>r|| r>=n) { throw new ExceptionBoundaryViolation(“Error”); }
Object bak = A[r];
for (int i = r; i<n; i++) { A[i] = A[i+1]; } //
n- - ; //update the size of the vector
return bak;
}
}
O(N);
Extend the Size of the Vector
if n>=N, insertAtRank()
#1 Create a new 2N new array B
#2 Copy all elements in A[] to B[]
#3 Replace A back to B
public class VectorExtArray implements Vector {
private int N = 8; //initial capacity N
private int n;
private Object A[];
public VectorExtArray() {
A = new Object[N];
n = 0;
}
public int getSize() { return n; }
public boolean isEmpty() {
return (0 == n) ? true : false;
}
public Object getAtRank(int r) throws ExceptionBoundaryViolation {
if ( 0 > r || r >= n ) { throw new ExceptionBoundaryViolation(“Error”); }
return A[r];
}
public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
if ( 0 > r || r >= n ) { throw new ExceptionBoundaryViolation(“Error”); }
Object bak = A[r];
A[r] = obj;
return bak;
}
public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation {
if ( 0 > r || r > n) { throw new ExceptionBoundaryViolation(“Error”); }
if ( N <= n) {
N * = 2;
Object B[] = new Object[N]; // create a new array 2N
for ( int i = 0; i<n; i++) {
B[i] = A[i]; // copy all elements from A[] to B[]
}
A = B;
}
for(int i = n; i> r; i- - ) { A[i] = A[i -1]; }
A[r] = obj;//insert
n++;
return obj;
}
public Object removeAtRank(int r) throws ExceptionBoundaryViolation {
if ( 0> r || r>=n) { throw new ExceptionBoundaryViolation(“Error”); }
Object bak = A[r];
for(int i = r; i< n-1; i++) { A[i] = A[i+1]; }
n- - ;
return bak;
}
}
java.util.ArrayList and java.util.Vector Classes
Vector is similar with ArrayList, but it is synchronized.
ArrayList is a better choice if your program is thread-safe.
Vector and ArrayList require space as more elements are added. Vector each time doubles its array size, while ArrayList grow 50% of its size each time.
ArrayList
methods - first(), last(), getPrev(p); getNext(p); replace(p, e); insertFirst(e); insertLast(e); insertBefore(p, e); insertAfter(p, e);
remove(p);
method: insertBefore(p, e)
inputs: position p, item e
outputs: insert item e before position p
{
create a new node v;
v.setElement(e); //store the item e in node v
v.setPrev(p.getPrev); //link the p’s prev
(p.getPrev()).setNext(v); //link p’s prev
p.setPrev(v); //p will be the next of v
return ((Position)v); //
}
insertAfter(), insertFirst(), insertLast will all be similar
remove(p) Algorithm
method: remove(p)
inputs: Position p
outputs: remove the item e in position p, return e
{
bak = p.element; // backup the current item
(p.getNext()).setPrev(p.getPrev); //link p’s next with p’s previous
(p.getPrev()).setNext(p.getNext);
p.setNext(null); //isolate item p
p.setPrev(null); //isolate item p
return bak;
}
Final List Implementation with Double End Node
public class ListDLNode implements List {
protected int numElem; //size of items
protected DLNode header, trailer; // first node and last node
public ListDLNode(){
numElem = 0; //empty
header = new DLNode(null, null, null); //first
trailer = new DLNode(null, header, null); //tailer
header.setNext(trailer); //link header and trailer
}
protected DLNode checkPosition(Position p) throws ExceptionPositionInvalid {
if (null == p){
throw new ExceptionPositionInvalid(“Error, position is null”);
}
if(header == p){
throw new ExceptionPositionInvalid(“Error, header is invalid position”);
}
if(trailer == p){
throw new ExceptionPositionInvalid(“Error, trailer is invalid position”);
}
DLNode temp = (DLNode)p;
return temp;
}
public int getSize() { return numElem; }
public boolean isEmpty() { return (numElem == 0); }
public Position first() throws ExceptionListEmpty {
if(isEmpty()){
throw new ExceptionListEmpty(“Error: empty list”);
}
return header.getNext();
}
public Position last() throws ExceptionListEmpty {
if(isEmpty()){
throw new ExceptionListEmpty(Error: empty list“");
}
return trailer.getPrev();
}
public Position getPrev(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation{
DLNode v = checkPosition(p);
DLNode prev = v.getPrev();
if(prev == header){
throw new ExceptionBoundaryViolation(“error: reach the header of list”);
}
return prev;
}
public Position getNext(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation {
DLNode v = checkPosition(p);
DLNode next = v.getNext();
if(next == trailer){
throw new ExceptionBoundaryViolation(“error: reach the trailer”);
}
return next;
}
public Position insertBefore(Position p, Object element) throws ExceptionPositionInvalid {
DLNode v = checkPosition(p);
numElem++;
DLNode newNode = new DLNode(element, v.getPrev(), v);
v.getPrev().setNext(newNode);
v.setPrev(newNode);
return newNode;
}
public Position insertAfter(Position p, Object element) throws ExceptionPositionInvalid {
DLNode v = checkPosition(p);
numElem++;
DLNode newNode = new DLNode(element, v, v.getNext());
v.getNext().setPrev(newNode);
.vsetNext(newNode);
return newNode;
}
public Position insertFirst(Object e){
numElem++;
DLNode newNode = new DLNode(e, header, header.getNext());
header.getNext().setPrev(newNode);
header.setNext(newNode);
return newNode;
}
public Position insertLast(Object e) {
numElem++;
DLNode newNode = new DLNode(e, trailer.getPrev(), trailer);
if(null == trailer.getPrev()) {
System.out.println(“!!!prev is null, that is impossible!!!");
}
trailer.getPrev().setNext(newNode);
trailer.setPrev(newNode);
return newNode;
}
public Object remove(Position p) throws ExceptionPositionInvalid {
DLNode v = checkPosition(p);
numElem- - ;
DLNode vPrev = v.getPrev();
DLNode vNext = v.getNext();
vPrev.setNext(vNext);
vNext.setPrev(vPrev);
Object vElem = v.getElem();
v.setNext(null);
v.setPrev(null)
return vElem;
}
public Object removeFirst() { return remove(header.getNext()); }
public Object removeLast() { return remove(trailer.getPrev()); }
public Object replace(Position p, Object obj) throws ExceptionPositionInvalid {
DLNode v = checkPosition(p);
Object oldElem = v.getElem();
v.setElem(obj);
return oldElem;
}
}
References:
https://stackoverflow.com/questions/2986296/what-are-the-differences-between-arraylist-and-vector
发表评论
-
Interview(8)Dictionary and Tree
2017-07-28 04:22 500Interview(8)Dictionary and Tree ... -
Interview(7)Map and Hash Table
2017-07-21 06:10 602Interview(7)Map and Hash Table ... -
Interview(6)Priority Queue
2017-07-15 04:41 516Interview(6)Priority Queue Pri ... -
Interview(5)Binary Tree
2017-07-06 04:23 632Interview(5)Binary Tree Binary ... -
Interview(4)Sequence Iterator and Tree
2017-06-30 00:34 600Interview(4)Sequence Iterator a ... -
Interview(2)Stack and Queue
2017-06-13 04:15 592Interview(2)Stack and Queue St ... -
Interview(1)Algorithm Book
2017-06-09 04:37 560Interview(1)Algorithm Book Cha ... -
Mysql Database Event and Procedure(1)MySQL Event
2016-12-07 03:42 696Mysql Database Event and Proced ... -
Algorithm Basic(1)Algorithm in Java
2014-10-02 12:20 647Algorithm Basic(1)Algorithm i ... -
Search and Parse Keyword(1)JACKSON for JSON and Jsoup for URL Fetch
2014-09-23 07:13 1312Search and Parse Keyword(1)JA ... -
Compiler Principle(2)Go and NodeJS
2014-08-06 22:10 603Compiler Principle(2)Go and Nod ... -
JAVA基础(一)equals和==和hashCode
2010-06-07 22:32 1325JAVA基础(一)equals和==和hashCode 根据 ... -
ThreadLocal笔记
2010-01-05 10:15 1297ThreadLocal笔记 网上搜索的结果,实践验证后记录 ... -
摘:JAVA面试(四)
2010-01-05 10:15 1381摘:JAVA面试(四) 1、RDBM ... -
摘:JAVA面试题目(三)
2010-01-05 10:14 1289JAVA面试题目(三) 1、两个对象值相同(x.equals ... -
摘:JAVA面试题目(二)
2010-01-05 10:14 1484JAVA面试题目(二) 1、erro ... -
摘:JAVA面试题目(一)
2010-01-05 10:14 1482JAVA面试题目(一) 水平一流,但往往栽在基础知识的问题上 ...
相关推荐
1、List集合:ArrayList、LinkedList、Vector等 2、Vector是List接口下线程安全的集合 3、List是有序的 4、Array
4. **STL(标准模板库)**:容器(如vector, list, map)、迭代器、算法。 5. **异常处理**:try-catch机制和异常类型。 6. **RAII(Resource Acquisition Is Initialization)**:智能指针和资源管理。 然后是...
1. **容器**:熟悉vector、list、deque、stack、queue、set、map等容器的特性和使用场景。 2. **迭代器**:理解迭代器的概念,能够使用迭代器遍历容器中的元素。 3. **算法**:掌握STL提供的常用算法,如sort、find...
- 包含List(如LinkedList、ArrayList和Vector)、Set(如HashSet、TreeSet)和Map(如Hashtable、HashMap、WeakHashMap)等接口和实现类。自定义数据结构通常涉及实现这些接口。 9. **异常处理**: - Java使用...
6. 标准库:熟悉STL(标准模板库),包括容器(如vector、list、map)、迭代器、算法等,能提高代码效率。 7. 动态内存与智能指针:使用new/delete进行动态内存管理,同时学习智能指针(如unique_ptr、shared_ptr)...
面试中可能会涉及如何使用STL(Standard Template Library)容器,如vector、list、set、map等。 3. **数据结构**:数据结构是理解和解决问题的基础,包括数组、链表、栈、队列、树(二叉树、AVL树、红黑树等)、图...
5. **STL(Standard Template Library)**:熟悉容器(如vector、list、map等)、算法和迭代器的使用。 6. **异常处理**:理解try、catch和throw语句,以及如何有效地处理程序运行时可能出现的错误。 7. **内存...
- 标准模板库(STL)的基础知识,包括容器(vector, list, set, map等),迭代器,算法。 - C++标准库的使用,如iostream,fstream,string等。 以上内容涵盖了C语言面试中可能遇到的主要知识点,熟练掌握这些...
集合框架主要分为LIST、SET和MAP三大接口,涵盖了如ArrayList、Vector、LinkedList、HashSet、TreeSet、HashMap、ConcurrentHashMap等常用集合类。掌握这些集合类的原理和使用场景,例如ArrayList和LinkedList在插入...
STL(Standard Template Library,标准模板库)是C++的一个重要组成部分,它包含了一系列的容器(如vector、list、set等)、迭代器、算法和函数对象。熟悉STL的使用可以极大地提高编程效率,也是面试中经常被问到的...
- **容器**:如vector, list, set, map等,以及它们的基本操作和迭代器的使用。 - **算法**:如排序、查找、交换等,掌握它们的使用场景和效率。 - **迭代器**:理解迭代器的工作原理,以及如何通过迭代器遍历...
5. **STL(Standard Template Library)**:熟悉容器(如vector, list, set, map等)、迭代器、算法和函数对象(如std::sort, std::find, std::transform等)的使用。 6. **异常处理**:理解何时抛出和捕获异常,...
3. **容器与算法**:C++标准库中的容器(如vector,list,set,map等)和算法(如sort,find,transform等)提供了丰富的工具来组织和操作数据。熟练使用这些工具能提高代码效率和可读性。 4. **面向对象编程**:...
- **STL(标准模板库)**:熟悉容器(如vector, list, map等)、算法和迭代器的使用。 3. **C++高级特性** - **异常处理**:理解try-catch结构,学会在程序中捕获和处理异常。 - **命名空间**:使用namespace...
- 容器(如vector、list、set、map等):了解其工作原理和应用场景。 - 迭代器:使用迭代器遍历容器中的元素。 - 预定义算法(如sort、find、transform等):利用这些算法简化编程任务。 8. **异常处理**: - ...
11. 标准模板库(STL):熟悉容器(如vector、list、set、map等)的使用,掌握迭代器的操作。 12. 算法:掌握排序(如快速排序、归并排序、堆排序)和搜索(如二分查找、线性查找)的基本思想和实现。 13. 泛型编程:...
3. **STL(标准模板库)**:STL是C++中的一个重要组成部分,提供了容器(如vector、list、set、map)、迭代器、算法和内存管理工具。熟悉STL的使用能提高代码效率和可读性。 4. **模板**:C++中的模板允许创建泛型...
同时,了解STL(Standard Template Library)的容器(如vector、list、set等)、迭代器和算法。 4. **内存管理**:掌握动态内存分配(new和delete操作),理解栈和堆的区别,以及智能指针(如unique_ptr、shared_...
STL是C++标准库的一部分,包含容器(如vector、list、set等)、迭代器、算法和函数对象。熟练运用STL可以简化代码,提高开发效率。 9. **内存管理** C++提供了手动内存管理,包括new/delete操作符以及智能指针。...