1.单链表的定义和由来:
链表是用一组地址可能连续也可能不连续的存储单元来存储线性表中的数据元素,在存储数据元素时,除了要存储数据元素本身之外,还要存储与它相邻的数据元素的地址信息,这两部分组成了线性表中一个数据元素的映像,称之为"结点",存储数据元素本身的部分称之为:数据域,存储相邻数据元素地址的部分称之为:地址域,所有节点通过地址域链接起来,像一个链条,故用此种方式存储的线性表称之为:链表.如果节点的地址域只存储了数据元素的直接后继的存储地址,则称这种链表为:单链表.
与数序表相比,链表由于是通过存储后继结点地址的方式来体现线性关系的,向链表中插入,删除数据元素要比顺序表要快(因为顺序表对数据元素的插入和删除操作时,大部分情况下,要对数据元素在存储单元中做移动);但是查找链表中的数据元素要比顺序表中的查找要慢,因为查找链表中的数据元素,需要遍历链表(而顺序表由于每个元素与第一个元素的地址相对固定,所以只要知道第一个数据元素的地址和数据元素的数据类型,很快就会直接定位到要查找的数据元素).
结点:
2.单链表的实现:
2.1结点:
Node
public class Node<T>
{
private T _data;
public T Data
{
get { return _data; }
set { _data = value; }
}
private Node<T> _next;
public Node<T> Next
{
get { return _next; }
set { _next = value; }
}
public Node()
{
_data = default(T);
_next = null;
}
public Node(T data)
{
_data = data;
_next = null;
}
public Node(Node<T> next)
{
_next = next;
}
}
2.2单链表:
SepLinkedList
public class SepLinkedList<T>
{
private Node<T> _head;
///
/// 头指针
///
public Node<T> Head
{
get { return _head; }
set { _head = value; }
}
///
///
获取单链表长度
///
///
public int GetLength()
{
Node<T> p = _head;
int length = 0;
while (p != null)
{
length++;
p = p.Next;
}
return length;
}
///
/// 清空单链表
///
public void Clear()
{
_head = null;
}
public bool IsEmpty()
{
if (_head == null)
{
return true;
}
else
{
return false;
}
}
///
/// 附件数据元素
///
///
public void Append(T item)
{
Node<T> p = new Node<T>();
Node<T> q = new Node<T>(item);
if (_head == null)
{
_head = q;
return;
}
p = _head;
while (p.Next != null)
{
p = p.Next;
}
p.Next = q;
}
///
/// 删除第i个数据元素
///
///
///
public T Delete(int i)
{
Node<T> q = new Node<T>();
if (i == 1)
{
q = _head;
_head = _head.Next;
return q.Data;
}
Node<T> p = _head;
int j = 1;
while (p.Next != null && j < i)
{
j++;
q = p;
p = p.Next;
}
if (j == i)
{
q.Next = p.Next;
return p.Data;
}
else
{
Console.WriteLine("该位置不存在结点");
return default(T);
}
}
///
/// 在第i个位置前插入数据元素
///
///
///
public void Insert(T item, int i)
{
if (i == 1)
{
Node<T> q = new Node<T>(item);
q.Next = _head;
_head = q;
return;
}
Node<T> p = _head;
Node<T> r = new Node<T>();
int j=1;
while (p.Next != null && j < i)
{
r = p;
p = p.Next;
}
if (j == i)
{
Node<T> q = new Node<T>(item);
q.Next = p;
r.Next&nb