真正的动态数据结构（引用和指针）
优点:真正的动态，不需要处理固定容量的问题。
缺点:丧失随机访问的能力。
链表就像寻宝，我们拿到藏宝图开始出发寻宝，每找到一个地方后，里面藏着下一步应该去哪里寻找。一步一步往下找，就能找到宝藏。每个节点都存有数据和下个节点的位置。
将数据存储在节点中,next指向当前节点的下一个节点。
class Node
{
E e;
Node next;
}
要想访问这个链表的所有节点，我们必须知道链表的头节点，所以我们定义head，在定义个size记录链表中有几个元素
向链表的头添加元素很简单，我们添加一个node，在把这个nodet指针指下一个节点，这时的head节点就变成我们添加的节点，我们就变成头节点。
所以LinkList类
package com.dsideal.test; public class LinkList<E>
{
private class Node
{
public E e; public Node next; public Node(E e, Node next)
{
this.e = e;
this.next = next;
}
public Node(E e)
{
this(e,null);
}
public Node()
{
this(null,null);
}
@Override
public String toString()
{
return e.toString();
}
} private Node head; private int size; public LinkList()
{
head = null;
size = 0;
} public int getSize()
{
return size;
} public boolean isEmpty()
{
return size == 0;
} public void addFirst(E e)
{
// Node node = new Node(e);
// node.next = head;
// head = node; head = new Node(e,head);
size ++;
}
}
在链表中间添加元素，我们必须知道在插入节点之前的一个节点是什么。将前一个节点的指针指向我们插入的节点，把我们的插入节点的指针指向下一个节点。
package com.dsideal.test;
public class LinkList<E>
{
private class Node
{
public E e; public Node next; public Node(E e, Node next)
{
this.e = e;
this.next = next;
}
public Node(E e)
{
this(e,null);
}
public Node()
{
this(null,null);
}
@Override
public String toString()
{
return e.toString();
}
} private Node head; private int size; public LinkList()
{
head = null;
size = 0;
} public int getSize()
{
return size;
} public boolean isEmpty()
{
return size == 0;
} public void addFirst(E e)
{
// Node node = new Node(e);
// node.next = head;
// head = node; head = new Node(e,head);
size ++;
} public void add(int index,E e)
{
if (index < 0 || index > size)
{
throw new IllegalArgumentException("add is fail,index < 0 or index >= size");
}
if (index == 0)
{
addFirst(e);
}else {
Node prev = head;
for (int i = 0;i < index - 1;++i)
{
prev = prev.next;
}
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node; prev.next = new Node(e,prev.next);
size ++;
} } public void addLast(E e)
{
add(size,e);
} @Override
public String toString()
{
StringBuilder res = new StringBuilder();
res.append("Link head:");
Node cur = head;
while (cur != null)
{
res.append(cur + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}
这时我们发现，当add插入index等于零的时候，要做个判断。所以我们引入一个虚拟的头节点。Node dunmmy = new Node(null,null);删除节点，找到要删除节点的上一个节点，将
他的指针指向删除节点的下一个节点，将我们删除节点的next指向null。
所以LinkLIst类变为
public class LinkList<E>
{
private class Node
{
public E e; public Node next; public Node(E e, Node next)
{
this.e = e;
this.next = next;
} public Node(E e)
{
this(e, null);
} public Node()
{
this(null, null);
} @Override
public String toString()
{
return e.toString();
}
} private Node dummyHead; private int size; public LinkList()
{
dummyHead = new Node(null, null);
size = 0;
} //获取链表元素个数
public int getSize()
{
return size;
} //链表是否为空
public boolean isEmpty()
{
return size == 0;
} //增加链表头元素
public void addFirst(E e)
{
// Node node = new Node(e);
// node.next = head;
// head = node;
add(0, e);
} //增加链表元素个数
public void add(int index, E e)
{
if (index < 0 || index > size)
{
throw new IllegalArgumentException("index < 0 or index > size,add is fail.");
} Node prev = dummyHead;
for (int i = 0; i < index; i++)
{
prev = prev.next;
}
// Node node = new Node(e);
// node.next = prev.next;
// prev.next = node;
prev.next = new Node(e, prev.next);
size++;
} //添加链表末尾元素
public void addLast(E e)
{
add(size, e);
} //获取元素index
public E get(int index)
{
if (index < 0 || index >= size)
{
throw new IllegalArgumentException("get is fail,index < 0 or index > size");
}
Node cur = dummyHead.next;
for (int i = 0;i < index;++i)
{
cur = cur.next;
}
return cur.e;
} //获取第一个元素
public E getFirst()
{
return get(0);
} //获取最后一个元素
public E getLast()
{
return get(size - 1);
} //判读是否包含
public boolean contains(E e)
{
Node cur = dummyHead.next;
while (cur != null)
{
if (cur.e.equals(e))
{
return true;
}
cur = cur.next;
}
return false;
} //修改值
public void set(int index,E e)
{
if (index < 0 || index >= size)
{
throw new IllegalArgumentException("set is fail,index < 0 or index > size");
}
Node cur = dummyHead.next;
for (int i = 0;i < index;++i)
{
cur = cur.next;
}
cur.e = e;
} //删除元素
public E remove(int index)
{
if (index < 0 || index >= size)
{ }
Node prev = dummyHead;
for (int i = 0;i < index;++i)
{
prev = prev.next;
}
//删除的元素
Node retNode = prev.next;
prev.next = retNode.next;
retNode.next = null;//删除元素的指向下一个地址为空
size-- ;
return retNode.e;
}
//删除第一元素
public E removeFirst()
{
return remove(0);
}
//删除最后一个元素
public E removeLast()
{
return remove(size - 1);
}
@Override
public String toString()
{
StringBuilder res = new StringBuilder("");
for (Node cur = dummyHead.next; cur != null; cur = cur.next)
{
res.append(cur + "->");
}
res.append("NULL");
return res.toString();
}
}
用链表实现栈
public class LinkListStack<E> implements Stack<E>
{
private LinkList<E> linkList; public LinkListStack()
{
linkList = new LinkList<>();
} @Override
public int getSize()
{
return linkList.getSize();
} @Override
public boolean isEmpty()
{
return linkList.isEmpty();
} @Override
public void push(E e)
{
linkList.addFirst(e);
} @Override
public E pop()
{
return linkList.removeFirst();
} @Override
public E peek()
{
return linkList.getFirst();
} @Override
public String toString()
{
StringBuilder res = new StringBuilder();
res.append("Stack top[");
res.append(linkList);
res.append("] tail");
return res.toString();
}
}
链表实现队列，优化算法变为O(1)级别的
public class LinkListQueue<E> implements Queue<E>
{
//内置节点
private class Node
{
public E e; public Node next; public Node(E e,Node next)
{
this.e = e;
this.next = next;
} public Node(E e)
{
this(e,null);
} public Node()
{
this(null,null);
}
@Override
public String toString()
{
return e.toString();
}
} private Node head,tail; private int size; public LinkListQueue()
{
head = null;
tail = null;
size = 0;
} @Override
public int getSize() {
return size;
} @Override
public boolean isEmpty() {
return size == 0;
} @Override
public void enqueue(E e) {
if (tail == null)
{
tail = new Node(e);
head = tail;
}else {
tail.next = new Node(e);
tail = tail.next;
tail.next = null;
}
size ++;
} @Override
public E dequeue() {
if (isEmpty())
{
throw new IllegalArgumentException("dequeue is fail,queue is isEmpty");
}
Node retNode = head;
head = retNode.next;
retNode.next = null;
if (head == null)
{
tail = null;
}
size--;
return retNode.e;
} @Override
public E getFront() {
if (isEmpty())
{
throw new IllegalArgumentException("Queue is isEmpty,so getFront is fail.");
}
return head.e;
}
@Override
public String toString()
{
StringBuffer str = new StringBuffer("");
str.append("LinkListQueue: head:");
Node cur = head;
while (cur != null)
{
str.append(cur + "->");
cur = cur.next;
}
str.append("NULL");
return str.toString();
}
}