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

2019/04/10 10:10

• 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);
}
}


    public boolean add(E e) {
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++;
}



rangeCheckForAdd 检查插入位置有没有超过数组大小。则直接抛出异常

### 查找指定下标 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> {
E item;
Node<E> next;
Node<E> prev;

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


    void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}


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


### get(i) 查找

    Node<E> node(int index) {
// assert isElementIndex(index);

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



### remove(i)

    E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> 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<String> strings = new ArrayBlockingQueue<String>(2);


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

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

## 小结

• 顺序表 ArrayList
• 栈 Stack
• 队列 Queue

## 参考：

http://c.biancheng.net/view/3352.html

0
0 收藏

0 评论
0 收藏
0