# 数据结构 1 线性表详解 链表、 栈 、 队列 结合JAVA 详解

• List
• Set
• MAP
• Queue

• 顺序表
• 链表
• 队列

## 顺序表

String [] array = new String[] {"a","b","c"};

JAVA 里面我们知道最基本的List 接口，下面有一个 ArrayList
ArrayList 底层就是以一个数组，其就是一个顺序表。

### 基本操作

public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}

ensureCapacityInternal(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;
}

ensureCapacityInternal 是对数组的监测，若大小不足以容纳，则扩容的机制

public void add(int index, E element) {

ensureCapacityInternal(size + 1);  // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}

### 查找指定下标 get()

public E get(int index) {
rangeCheck(index);

return elementData(index);
}

### remove() 移除元素

public E remove(int index) {
rangeCheck(index);

modCount++;
E oldValue = elementData(index);

int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work

return oldValue;
}

## 链表

private static class Node {
E item;
Node next;
Node prev;

Node(Node prev, E element, Node next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}

final Node l = last;
final Node newNode = new Node(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}

void linkBefore(E e, Node succ) {
// assert succ != null;
final Node pred = succ.prev;
final Node newNode = new Node(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}

### get(i) 查找

Node node(int index) {
// assert isElementIndex(index);

if (index > 1)) {
Node x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

### remove(i)

// assert x != null;
final E element = x.item;
final Node next = x.next;
final Node prev = x.prev;

if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}

if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}

x.item = null;
size--;
modCount++;
return element;
}

## 队列 Queue

BlockingQueue strings = new ArrayBlockingQueue(2);

### 出队 poll()/take()

• poll检索并删除此队列的头，如果此队列为空，则返回 null 。
• take 在没有元素的时候则会阻塞

## 小结

• 顺序表 ArrayList