数据结构（四）——链表
之前的数组、栈和队列三篇博客中，都依托封装的静态数组实现了动态扩容，对用户来说达到了相当于动态数据结构的效果；链表则是一种真正的线性动态数据结构，本身就是支持动态扩容的；链表的数据存放在节点中，这个节点还存储了一个next指向下一个节点。如果一个节点的next为空则表示这个链表的最后一个节点；对于链表，不需要进行扩容，直接进行追加即可；删除某个节点时只需要更改这个节点前一个节点的next，更改为此节点的下一个节点即可；但是链表丧失了直接访问的能力，因为数组开辟的空间是连续的，我们可以通过地址偏移直接访问元素，链表只能通过next进行遍历，即链表增删快，查找慢；
链表是由一个一个的节点连接起来的，显然需要一个Node类表示节点，这个节点中不仅需要存储数据，还需要存储下一个节点；那么Node类如下：
public class Node<E>{
private Node next;
private E e;
public Node(E e) {
this.e = e;
next = null;
}
public Node(E e,Node next) {
this.e = e;
this.next = next;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public E getE() {
return e;
}
public void setE(E e) {
this.e = e;
}
@Override
public String toString() {
return e.toString();
}
}对于一个链表，无非还是增删改查；下面是一个简单的实现：
package com.gby.about_list;
public class LinkedListDemo<E> {
public class Node<E>{
private Node next;
private E e;
public Node(E e) {
this.e = e;
next = null;
}
public Node(E e,Node next) {
this.e = e;
this.next = next;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public E getE() {
return e;
}
public void setE(E e) {
this.e = e;
}
@Override
public String toString() {
return e.toString();
}
}
private int size;
private Node head;
public LinkedListDemo() {
head = null;
size = 0;
}
/**
* @return int
* 返回链表中元素的个数
*/
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++;
}
/**
* @param i
* @param e
* 在第index+1个元素的位置插入一个数据e
*/
public void add(int index ,E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("Add failed.Index is illegal.");
}
if(index == 0){
addFirst(e);
}else{
Node prev = head;
for(int i = 0;i<index-1;i++){
prev = prev.next;
}
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("linkedList:[");
Node prev = head;
for(int i=0; i < size;i++){
res.append(prev);
prev = prev.next;
if(i!=size-1){
res.append(",");
}
}
res.append("]");
return res.toString();
}
}思路：
1. Node是专属于这个LinkedList的，把它放作一个内部类；一个Node节点包含数据和下一个节点，即E e和Node next两个成员变量；
2. 对一个链表，需要链表头和链表的大小。即Node head和int size两个属性；
3. 提供构造方法，判空和获取链表大小的方法：构造方法默认创建一个空的链表，head为null，size为0；
4.向链表的某个位置添加元素时，把要存放的数据封装在Node节点中，让新节点的next为该位置下一个节点，该位置前一个节点的next更改为新的节点：比如：原本node1.next = node3;现在插入node2，让node2.next = node3,再让node1.next=node2；就把node2插入进去了；
这种方式无法在下标为0的位置添加元素，因为需要依赖index=0的前一个节点即prev；怎么解决呢？：
下标为0的位置即为head的位置；新建一个节点，将新节点node的next指定为head.next，再把node当做新的head;
5.删除操作：
把前一个节点的next修改为index的后一个节点，被删除节点的next赋值为null,那么这个节点就不在链表中了；显然，这种删除还是需要新建一个删除方法来删除原来的链表头；
怎么使用一种统一的方法进行删除和插入，不必考虑是否是同一个元素呢？上面的方法之所以需要分开讨论是因为头结点head为第一个node,他没有前驱节点prev；如果我们把第一个数据所在的节点之前加入一个虚拟头结点，把第一个数据和后面的数据一视同仁就可以解决这个问题；修改后的代码如下：
package com.gby.about_list;
public class LinkedList<E> {
public class Node<E>{
private Node next;
private E e;
public Node(E e) {
this.e = e;
next = null;
}
public Node(E e,Node next) {
this.e = e;
this.next = next;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public E getE() {
return e;
}
public void setE(E e) {
this.e = e;
}
@Override
public String toString() {
return e.toString();
}
}
private int size;
private Node dummyHead;
public LinkedList() {
dummyHead = new Node<E>(null,null);
size = 0;
}
/**
* @return int
* 返回链表中元素的个数
*/
public int getSize(){
return size;
}
public boolean isEmpty(){
return size == 0;
}
//在链表头添加节点
public void addFirst(E e){
add(0, e);
}
/**
* @param i
* @param e
* 在第index+1的元素的位置插入一个数据e，即想象一个数组，在下标为index的位置插入一个数据e
*/
@SuppressWarnings("unchecked")
public void add(int index ,E e){
if(index < 0 || index > size){
throw new IllegalArgumentException("index is illegal.");
}
Node prev = dummyHead;
for(int i = 0;i < index;i++){
prev = prev.next;
}
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("linkedList:");
Node prev = dummyHead;
for(int i=0; i < size;i++){
prev = prev.next;
res.append(prev);
if(i!=size-1){
res.append("->");
}
}
return res.toString();
}
public E get(int index){
if(index<0 || index >size){
throw new IllegalArgumentException("index is illegal.");
}
Node cur = dummyHead.next;
for(int i=0;i < index;i++){
cur = cur.next;
}
return (E) cur.e;
}
public E getFirst(){
return get(0);
}
public E getLast(){
return get(size -1);
}
public void set(int index,E e){
if(index<0 || index >size){
throw new IllegalArgumentException("Set failed.Index is illegal.");
}
Node cur = dummyHead.next;
for(int i=0;i < index;i++){
cur = cur.next;
}
cur.e = e;
}
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 E remove(int index){
if(index<0 || index >size){
throw new IllegalArgumentException("Remove failed.Index is illegal.");
}
Node prev = dummyHead;
for(int i=0;i<index;i++){
prev = prev.next; //每次遍历prev变为下标为i的位置；最终为index-1的位置
}
Node deleteNode = prev.next;
E e = (E) deleteNode.e;
prev.next = deleteNode.next;
deleteNode.next = null;
size--;
return e;
}
}虚拟头结点dummyHead的e为null；这样第一个数据节点就也有了一个前驱节点；只是，之后对链表的遍历就需要多遍历一次了。但是插入和删除就不必考虑是否是在头结点的位置了；
以上就是链表的实现。
上一篇： 数据库怎么建立索引
下一篇： 实例详解es6在react中的应用